《数据结构》试卷四含答案.docx

1、数据结构试卷四、选择题（此题共20分，每题1分）1.1.在数据结构中，从逻辑上可以把数据结构分成（A.动态结构和静态结构A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构C.线性结构和非线性结构D.内部结构和外部结构2.2.线性表假设采用链式存储结构时,要求内存中可用存储单元的地址（A.必须是连续的B.局部地址必须是连续的C. 一定是不连续的C. 一定是不连续的D.连续不连续都可以3.3.不带头结点的单链表head为空的判定条件是（A. head = NULLB. head->next =NULLC. head->next = headD. head! = NU

2、LL4.在一个单链表中，q所指结点是P所指结点的前驱结点，假设在q和p之间插入s结点，那么执行（A. snext=pnext; p-next=s; B. p->next=s->next; s-next=p;C. q->next=s; s->next=p;D. q->next=s; s->next=p;E. p-next=s; s->next=q;5.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比拟（平均比拟（）个结点。A. nB. n/2D. (n+l)/26.一个栈的入栈序列是a, b, c, d, e,那么栈的不可能

3、的输出序列是（)o7.A. edcbaB. decbaC. dceabD.abcde判定一个循环队列QU （最多元素为m0)为满队列的条件是（)oA. QU->front=QU->rearA. QU->front=QU->rearB. QU->front!=QU->rearC. QU->front (QU->rear+l) %C. QU->front (QU->rear+l) %mOD.QU->front!=(QU->rear+l) % mO8.8.栈和队列的共同点是（A.都是先进后出B.都是先进先出C.只允许在端点处插入

4、和删除元素D.没有共同点9.数组A中，每个元素A的长度为3个字节，行下标i从1到8,歹U下标j从1至U10,2.3.d a解：使用普里姆算法构造棵最小生成树的过程如下图DEFBACo中序遍历的结果是:转换的森林如下图:4.最终结果如图:5. 46删除之前和删除之后的两个结果分别如下列图所示H(13)=2H(13)=26.11(12)=1冲突Hf2冲突，H2=3H (34)=1冲突冲突，H2=3冲突,H(38)=5H (33)=0H(2)=2H(2)=2冲突,H尸3冲突,H2=4冲突，H3=5冲突,H4=611(22)=0冲突,HlI冲突,H2=2冲突,H4=4冲突，I5冲突，&二6冲8

5、 9 10突，H7=733 1 13 12 34 38 2 22ASL=(1+1+3+4+1+1+5+8)/8=24/8=3五、算法题（此题共10分）void BubbleSort (SeqList R) int i, j； Boolean exchange;For( i=l;i<n;i+)exchange=false;for(j=l;j<=n-I;j+)if (Rj+1. key<Rj. key)RO=Rj+l; Rj+l=Rj ; Rj=RO;exchange=true;if (!exchange) return;从首地址SA开始连续存放在存储器内，该数组按行存放时，元素

6、A 8 5的起始地址为A. SA+141B. SA+144C. SA+222D. SA+22510.广义表（a, b）, c, d）的表尾是（)oA. aB. bC. (a, b)D. (c, d)IL设矩阵A是一个对称矩阵，为了节省存储，将其下三角局部（如下列图所示）按行序存放在一维数组Bl,n(n-1)/2中,对下三角局部中任一元素ai, j（ij）,在一维数组B的下标位置k的值是（)o%,I 册 213.某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（)oC. deabcD. cedbaA. acbedB. decab14.）不是完全二叉树。）种。15.

7、按照二叉树的定义，具有3个结点的二叉树有（A. 3B. 4C. 5D. 6设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包含的结点数至少为（)oA. 2hA. 2hB. 2h-lC. 2h+lD. h+1.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A. 1/2B. 1C. 2D. 4.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。A. nB. n+1C. n-1D. n/216 .一有向图的邻接表存储结构如下列图所示，根据有向图的深度优先遍历算法，从 顶点V1出发，所得到的顶点序列是（）。A. vl, v2, v3, v5, v4B.

8、vl, v2, v3, v5, v4C. vl, v2, v3, v4, v5C. vl, v3, v4, v5, v2D. vl, v3, v4, v5, v2E. vl, v4, v3, v5, v219 .采用顺序查找方法查找长度为20 .采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为)oA. nB. n/2C. (n+l)/221 .快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数二、填空题（此题共20分，每空1分）.根据数据元素之间的不同特征，通常有四类基本结构:、

9、和1 .下面程序段的时间复杂度是：ofor （i=0； i<n； i+）for (j=0； j<m； j+)Ai j>0；2 .向一个长度为n的线性表中的第i个元素(lWiWn)之前插入一个元素时，需向 后移动 个元素。3 .在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：(1) s->next= ;(2) p-next=s;(3) t=p->data;(4) p->data= ;(5) s->data= ;.深度为k的完全二叉树至少有一个结点，至多有一个结点，假设按自上而下，从 左到右次序给结点编号(从1开始)，那么编号最小的叶子

10、结点的编号是 o4 . 一个广义表为(a, (a, b), d, e, (i, j), k),那么该广义表的深度为。5 .有一棵树如下列图所示，回答下面的问题：结点k3的度是；这棵树的度为 ； 这棵树的深度是 。.在对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序时，当把第七个记录60插入到有序表时，为寻找插入位置需比拟 次。6 .队列的插入操作在 进行，删除操作在 进行。7 .判定一个有向图中是否存在回路，即是否含有环，可以使用 方法。三、阅读程序写结果(此题共20分，每题5分).单链表中，指针P指向某结点，执行以下操作后，请用一句话描述程序

11、执行的结 果是什么？q=p->next;p->data=p->next->data;p->next= p->next->next;free (q);1 .阅读下面二分查找程序代码，填充空白位置，使算法完整。 int BinSearch (SeqList R, KeyType k) int low=l, high=n, mid;while(1ow<=high) mid=(low+high)/2;if (Rmid. key=k) return mid;if (Rmid. key>k) ;else ;return 0;.如下列图所示给出了图G及对

12、应的邻接表，根据给定的dfs算法，从顶点8出 发，写出其搜索序列。Adjlist gl;void dfs(int v) struct vexnode *p;printf (%d，v);visitedv=l;P=glv->link;/* gl是该图的邻接表的表头指针数组*/while (p!=NULL) if (visitedp->adjvex-0) dfs (p->adjvex);p=p->next;二 HZQ-HZEWZE03HZHE-*03-*izei4 03Hll303-012 .二叉树采用二叉链表存储结构，将第四题综合题3中的二叉树，运行下面的递归 算法，请写出

13、最后的返回结果是什么？int count (btree *b) int numl, num2;if (b=NULL) return(0);else if (b->left=NULL && b->right=NULL) return (1);else numl=count (b->left);num2=count (b->right);return (numl+num2);四、综合题(此题共30分，每题5分)1.有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为 4、7、 5、2、9,试画出对应的哈夫曼树(注意：构造哈夫曼树过程中请按左子

14、树根结点的权 值小于等于右子树根结点的权值次序构造)，并求出每个字符的哈夫曼编码。2 .利用普里姆算法，从节点1出发构造出如下列图所示的图G的一棵最小生成树。3 . 一棵二叉树如下面的图所示，要求：(1)写出对此二叉树进行中序遍历时得到的结点序列。(2)画出由此二叉树转换得到的森林。4 .请画出，将元素3和元素6依次插入到下列图所示的平衡二叉树中的结果，要求仍然 保持为一棵平衡二叉树。5 . 一组元素为(46, 25, 78, 62, 12, 37, 70, 29),要求：(1)画出按元素排列顺序输入生成的一棵二叉排序树。(2)画出在二叉排序树中，删除元素46后的结果.设哈希表长度为11,哈希

15、函数h(key);key % llo给定的关键字为1, 13, 12, 34, 38, 33, 2, 22。试画出用线性探查法解决冲突时所构造的哈希表。并计算在查找成 功时候的平均查找长度。五、算法题(此题共10分)假设线性表中包含n个数据元素，请写出顺序存储方式下对n个元素的冒泡排序算法。具体存储结构如下:#define Maxsize 20Typedef int KeyType;Typedef struct KeyType key;/关键字项InfoType otherinfo; 其它数据项 RedType;记录类型Typedef struct RedType r Maxsize+1 ; r 0闲置或者用做哨兵单元Int length;顺序表长度 SqList;顺序表类型参考答案一、选择题（此题共20分，每题1分）12345678910CDACDCCCCD11121314151617181920BDCCBBCCCC二、填空题（此题共20分，每空1分）.集合、线性结构、树形结构、网状结构1 . 0 （m*n）.