07年(上)试卷C.doc

_学院_级_班 姓名_ 学号_（密）（封）（线）密 封 线 内 答 题 无 效20072008学年度第一学期期末考试数据结构试卷C卷答卷说明：1、本试卷共7页，五个大题，满分100分，120分钟完卷。 2、本次考试为闭卷考试。 题号一二三四五总分总分人分数得分评卷人一、单项选择题（每小题2分，共20分）1线性表的顺序存储结构是一种【 】的存储结构。 A随机存取 B顺序存取 C索引存取 D散列存取2在HASH函数H（key）=key % p 中，p应取【 】。A最接近该HASH表长（设为m, 下同）的一个整数 B奇数 C小于或等于m的最大素数 D偶数3稀疏矩阵一般的压缩存储方法有【 】。A二维数组和三维数组 B三元组顺序表和散列表C三元组顺序表和十字链表 D散列表和十字链表4在有n个结点的链表L中，访问第i个结点(i=1,2, n)的算法GetElem_L（L，i, &e）的时间复杂度为【 】。 AO（n） BO(1) CO() DO()5关键路径是事件网络中【 】。A从源点到汇点的最短路径 B从源点到汇点的最长路径C最长的回路 D最短的回路6在无向图中，所有顶点的度数之和是所有边数的【 】倍。A0.5 B1 C2 D4 7设有广义表D=(a,b,D)，其长度为【 】。A. 无穷大 B. 3C. 2 D. 58若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为【 】。Ai Bn=i Cn-i+1 D不确定9在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为【 】。Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front10链表适用于【 】查找。A顺序 B二分法 C顺序，也能二分法 D随机得分评卷人二、填空题（每空2分，共10分）1对具有n个顶点的连通图其生成树有且仅有_ _条边。2折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 比较大小。3已知某二叉树的先序序列为EBADCFHGI，中序序列为ABCDEFGHI ，则后序序列为 。4对于三维数组Amnp，即mnp数组，每个数组元素占据L个地址单元，则数组元素aijk的存储位置为：LOC(aijk)=LOC(a111)+ 。5一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个 。得分评卷人 三、判断题，用“”或“”确定以下说法错误或正确（每小题1分，共10分）1顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ ）2向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。 （ ）3如果两个串含有相同的字符，则这两个串相等。 （ ）4对任意一个有向图都能进行拓扑排序。 （ ）5排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。 （ ）6对无序表用折半查找比顺序查找快。 （ ）7若二叉树用二叉链表作存储结构，则在n个结点的二叉树链表中只有n1个非空指针域。（ ）8用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。 （ ）9一对表头和表尾能唯一确定非空广义表。 ( )10在一棵树中，如果结点A只有3个兄弟，而且B是A的双亲，则B的度是5。 （ ）得分评卷人四、简答题（每小题6分，共30分）1.假设字符a、b、c、d、e、f的使用次数分别是 4, 8, 14, 22, 25, 27，画出Huffman树，将该二叉树所有左分枝标记1，所有右分枝标记0，写出a、b、c、d、e、f的Huffman（哈夫曼）编码。2 已知待排序文件各记录的关键字顺序如下49 38 65 97 76 13 27 49 （1）请写出快速排序过程中第一趟的排序结果； （2）什么是排序算法的稳定性？请问快速排序是否稳定？3下图是用邻接表存储的图，画出此图，并根据该存储结构写出图中从v0点开始按广度优先遍历的结果。4描述以下三个概念的区别：头指针，头结点，表头结点。5什么是堆？设有如下数列7，10，13，15，4，20，19，8，构造出该数列的根为最小值的堆。得分评卷人五、用类C语言描述下列算法，并给出必要说明题（共30分）1给出求二叉树的双分支结点数目算法。（本小题8分）(提示：双分支结点是度为2的结点）/二叉树的存储表示 typedef struct BiTNode ElemType data; Stuct BiTNode * lchild,*rchild;/ 左右指针标志BiTNode,*BiTree给出算法Status TwoBiTree(BiTree T)。2.建立带头结点的单链表La，并删除所有等于数值x的结点。（本小题10分）已知线性表的单链表存储结构如下： typedef struct Lnode elemtype data; Lnode * next;Lnode,*LinkList;给出算法Status creatList( LinkList &La)、Status DeleteList( LinkList &La，ElemType x)，并给出必要的注释。3用算法实现：求给定顶点v的出度和入度。（本小题12分）已知图的弧的结点结构：typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 ArcNode;顶点的结点结构typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;图的结构定义：typedef struct AdjList vertices; int vexnum