《数据结构》模拟试题综合测试题带答案 (15)

1、数据结构模拟试题15一、填空题（每小题2分，共18分）1、 数据的逻辑结构在计算机中的基本存储结构有 和 。2、 算法的时间复杂度取决于 。3、 队列是 的线性表，其操作数据的基本原则是 。4、设有一个二维数组A0909，若每个元素占2个基本存储单元，A00的地址是200，若按列优先（以列为主）顺序存储，则A66的存储地址是 。5、 在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为 。6、 对于一个有n个顶点和e条弧的有向图，若采用正邻接链表存储，则表头向量的大小为 ，邻接表中的结点总数为 。7、若采用分块查找，要求线性表块内 ，块间 。8、对于文件，按其记录

2、的类型可将文件分为 文件、 文件。9、 外部排序的最基本方法是 ，其主要时间花费在 方面。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、下面程序段的时间复杂度是（ ）。 for (i=1；i<=m；i+)for (j=1；j<=n；j+) Aij=i+j;（A） O(m+n) （B） O(m) （C） O(n) （D） O(m*n)2、 判断一个循环队列Q（最多元素个数为m）为满队列的条件是（ ）。（A） Q.front=Q.rear ； （B） Q.front!=Q.rear ；（C） Q.front=(Q.rear+1)%m； （D） Q.front!=(

3、Q.rear+1)%m；3、 设有一个栈顶指针为top的顺序栈S，则将元素p压入栈S中的操作是（ ）。（A） Stop+ =p； （B） S+top =p；（C） Stop- =p； （D） S-top = p； 4、 广义表(a),(b),c),(d)的长度是 ，深度是 。（ ）（A） 3, 4 （B） 3, 3 （C） 4, 3 （D） 4, 45、 在二叉树中，指针P所指的结点是叶子结点的条件是（ ）。（A） P->Lchild !=NULL&& P->Rchild !=NULL ； （B） P->Lchild !=NULL&& P-&g

4、t;Rchild =NULL ；（C） P->Lchild =NULL&& P->Rchild !=NULL ； （D） P->Lchild =NULL&& P->Rchild =NULL ；6、 一棵二叉树，其先序遍历序列是abdghcefi，中序遍历序列是bgdhaecfi，则其后序遍历序列是( )。（A） ghdbiefca （B） ghdbeicfa（C） ghdbeifca （D） gdheibfca7、 若以4, 5, 6, 7, 8作为叶子的权值构造Huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)，则

5、其带权路径长度WPL为（ ）。（A） 60 （B） 61 （C） 73 （D） 698、 在无权图G的邻接矩阵中，若(Vi, Vj)或< Vi, Vj>属于G的边集，则对应元素Aij等于 ，否则等于 。（ ）（A） 1，1 （B） 1，0 （C） 0，1 （D） 0，09、 设有一组记录的关键字是（37，28，56，80，60，14，25，50），用快速排序法以第一个记录为基准得到的一次划分结果是（ ）。（A） 25，28，14，37，60，80，56，50 （B） 25，28，37，14，60，80，56，50 （C） 25，28，14，37，60，56，80，50 （D） 25

6、，28，37，14，56，80，60，50三、分析题（每题6分，共30分）1、设有一棵树如下图，请先将此树转换为二叉树，然后给出该二叉树的前序线索树和中序线索树。abdifchjeg2、 已知某有向图的逆邻接链表如下图所示，请先画出该有向图，然后给出其邻接矩阵和正邻接链表。4012312345385101834243619523、 将关键字序列（17，19，13，7，15，9，25）依此插入到初态为空的二叉排序树中，请画出建立二叉排序树T的过程；然后画出删除13之后的二叉排序树T1。4、 线性表的关键字集合21，25，28，19，42，57，15，43，17，36，49，27，65，共有13个

7、元素，已知散列函数为：H（k）= k MOD 13，采用线性探测法处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。5、 已知数据序列为35，29，22，16，17，9，38，27，13，45，请给出采用选择排序方法按非递减要求进行排序的过程。四、算法填空（每空2分，共20分）请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。1、在以L为头结点的双向链表中删除所有值为key的结点，结点结构定义如下。typedef struct Lnode ElemType data ; /* 数据域，保存结点的值 */ struct Lnode *prior ; /*

8、 指针域，指向直接后继 */struct Lnode *next ; /* 指针域，指向直接前趋 */DULNode; /* 结点的类型 */Void Del_Node(DULNode *L，int key) DULNode *q, *p=L>next ;while ( p!=NULL) if ( p>data=key ) q=p->next ;if ( p->next!=NULL) p->next->prior=p->prior ; ; else p->prior->next=NULL ; ; ; 2、设T是指向二叉树根结点的指针变量，用

9、非递归方法统计树中叶子结点的数目。#define Max_Node_Num 50Typedef struct BTNode ElemType data ; /* 数据域，保存结点的值 */struct BTNode *Lchild , *Rchild ; /* 指针域 */BTNode ; /* 结点的类型 */Void count_leaf_node ( BTNode *T) BTNode *StackMax_Node_Num ,*p=T, *q ;int top=0 , leaf_num=0 ; /* leaf_num 保存叶子结点的数目 */if (T=NULL) printf(“The

10、 Binary Tree is Empty!n”) ;else do if (p->Lchild=NULL&& p->Rchild=NULL) ;q=p->Rchild ; if ( q!=NULL ) ; p=p->Lchild ; while ( ) ; printf(“叶子结点的数目是: %dn”, leaf_num) ; 链表结点adjvexinfonextarc顶点结点indegreedatafirstarc3、用正邻接链表保存有向图，各结点的结构形式如下，所有的顶点结点放在数组adjlist中，统计图中顶点的入度。Void count_ind

11、egree(ALGraph *G) int k ; LinkNode *p ;for (k=0; k<G->vexnum; k+)G->adjlistk.indegree=0 ;for (k=0; k<G->vexnum; k+) ;while (p!=NULL) G->adjlistp->adjvex.indegree+ ; ; 4、H->Rsm中记录关键字除H->Rs.key均满足堆定义，调整H->Rs的位置使之成为小根堆。Void Heap_adjust(Sqlist *H, int s, int m) int j=s , k=

12、2*j ; /* 计算H->Rj的左孩子的位置 */ H->R0=H->Rj ; /* 临时保存H->Rj */ for (k=2*j ; k<=m ; k=2*k) if (k<m)&&(H->Rk.key>H->Rk+1.key) k+ ; /* 选择左、右孩子中关键字的最小者 */ if (H->R0.key>H->Rk.key) H->Rj=H->Rk ; j=k ;； else break ; ; 五、编写算法（要求给出相应的数据结构说明，14分）设Hash函数为H(key)=key

13、MOD 13，用链地址法解决冲突，请写出进行散列查找的算法。11数据结构模拟试题15参考答案一、填空题（每小题2分，共18分）1、 顺序（存储）结构 链式（存储）结构2、 问题的规模3、 操作受限 后进先出(先进后出)4、 2325、 2h-16、 n e7、 顺序存储 块间有序8、 操作系统 数据库9、 归并 内、外存之间的数据交换二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案DCBADCDBA三、分析题（每题6分，共30分）abfcgedijh图(a) 转换后的二叉树图(b) 前序线索树abfcgedijhNIL图(c) 中序线索树NILabfc

14、gedijh1、 解：转换后得到的二叉树如图(a)，前序线索树如图(b)，中序线索树如图(c)。2、 解：有向图如图(a)，其邻接矩阵如图 (b)，正邻接链表如图(c)。 图(a) 有向图12342589105644图(b) 有向图401231234 534194812210051634 9 8 4 5 6 4 2 10 （c） 邻接矩阵3、 解：将关键字序列（17，19，13，7，15，9，25）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除13之后的二叉排序树T1如图(b)所示。图(a) 生成的二叉排序树T的过程17191713191771319171571319

15、179157131917259157131917图(b) 删除13的二叉排序树T125157919174、 解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：H(31)=21 MOD 13=8 H(25)=25 MOD 13=12 H(28)=18 MOD 13=2H(19)=19 MOD 13=6 H(42)=42 MOD 13=3 H(57)=57 MOD 13=5H(15)=15 MOD 13=2 冲突 H(15)=(2+1) MOD 13=3 冲突H(15)=(3+1) MOD 13=4 H(43)=43 MOD 13=4 冲突 H(43)=(4+1) MOD 13=5 冲突

16、H(43)=(5+1) MOD 13=6 冲突 H(43)=(6+1) MOD 13=7H(22)=22 MOD 13=9 H(36)=36 MOD 13=10 H(49)=49 MOD 13=10 冲突 H(49)=(10+1) MOD 13=11 H(27)=27 MOD 13=1 H(65)=65 MOD 13=0 得到的散列表结构如下：0 1 2 3 4 5 6 7 8 9 10 11 12散列地址关键字65 27 28 42 15 57 19 43 31 22 36 49 25成功查找的平均查找长度：ASL=(1×9+2×2+2×3)/13=19/135

17、、 解：采用选择排序号方法做非递减排序的过程如下：35 29 22 16 17 9 38 27 13 45初始关键字：9 29 22 16 17 35 38 27 13 45第一趟排序：9 13 22 16 17 35 38 27 29 45第二趟排序：9 13 16 22 17 35 38 27 29 45第三趟排序：9 13 16 17 22 35 38 27 29 45第四趟排序：9 13 16 17 22 27 38 35 29 45第五趟排序：9 13 16 17 22 27 29 35 38 45第六趟排序：第六趟排序结束。四、算法填空（每空2分，共20分）请在下面各个算法的空白处

18、填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、在以L为头结点的双向链表中删除所有值为key的结点。p->prior->next=p->next free(p)p=q2、设T是指向二叉树根结点的指针变量，用非递归方法统计树中叶子结点的数目。leaf_num+stack+top=q p!=NULL 3、统计图中顶点的入度。P=G->adjlistk.firstarcP=p->nextarc4、H->Rsm中记录关键字除H->Rs.key均满足堆定义，调整H->Rs的位置使之成为小根堆。k=2*j H->Rj=H->R0五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定义及算法如下：#define M