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

1、数据结构模拟试题13一、填空题（每小题2分，共18分）1、 数据的逻辑结构包括 ， 和 三种结构。2、 队列是操作受限的线性结构，只能在 插入元素，而在 删除元素。3、 串是一种特殊的线性表，其特殊性体现在 。4、 有一个10阶对称矩阵A，采用压缩存储方式采用压缩存储方式，以行为主存储下三角形到一个一维数组中，A00的地址是100（每个元素占2个基本存储单元），则A59的地址是 。5、 在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为 。6、 对于一个有n个顶点和e条边的无向图，若采用邻接链表存储，则表头向量的大小为，邻接表中的结点总数为 。7、 对线性表进行

2、二分查找时，要求线性表必须是 ，且要求 。8、 对于文件，按物理结构划分，可分为顺序文件、 文件、 文件和多关键字文件。9、 外部排序的最基本方法是 ，其主要时间花费在 方面。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、如下函数是求1!+2!+n!，其时间复杂度是（ ）。Long int Sum (int n) long int sum=0 , t=1 ; int p ;for (p=1; p<=n ;p+) t=t*p ; sum+=t ; return(sum) ;（A） O(n) （B） O(n2) （C） O(2n) （D） O(n2n)2、 设有一个栈顶

3、指针为top的顺序栈S，则弹出S的栈定元素的操作是（ ）。（A） p=Stop+； （B） p=S+top；(C) p=Stop-； （D） p=S-top； 3、 广义表(a),(b),c),(d)的表头是 ，表尾是 。（ ）（A） (a) (b),c),(d) （B） (a) (b),c),(d)（C） (a),(b),c),(d) （D） (a) (d)4、一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，则其后序遍历序列是( )。（A） abdgehicf （B） gdbheiafc（C） gdhiebfca （D） gdheibfca5、 具有五层结点

4、的平衡二叉树至少有 。（ ）（A） 10 （B） 12 （C） 17 （D） 156、 在无权图G的邻接矩阵中，若(Vi,Vj)或< Vi,Vj>属于G的边集，则对应元素Aij等于 ，否则等于 。（ ）（A） 1，1 （B） 1，0 （C） 0，1 （D） 0，07、 判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ ）。(A) 广度优先遍历算法 (B) 求关键路径的方法(C) 深度优先遍历算法 (D) 求最短路径的Dijkstra算法8、设有一个长度为n的线性表，当采用顺序查找方法时，每个元素的平均查找长度是 ；而采用二分查找方法时，其平均查找长度是 。（ ）(

5、A) n/2 ,O(n) （B） n/2,O(2n) （C） (n+1)/2, O(n2n) （D） (n+1)/2, O(2n)9、 设有一组记录的关键字是（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，28，37，14，56，80，60，50三、分析题（每题6分，共30分）1、 设有一份电文中工使用了7个字符：a，b，c，d，s，m，n，它们出现的频

6、率依次为3，6，4，2，8，9，7，请画出对应的Huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)，并求其带权路径长度WPL。2、 对于下图中的网，写出该网的邻接链表；然后写出其深度优先搜索生成树（假设从顶点V3出发）；最后给出按Kruskal算法得到的最小生成树。1243812561173、 将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除13之后的二叉排序树T1；最后再后画出插入13之后的二叉排序树T2。4、 线性表的关键字集合31，25，18，29，42，67，15，33，17，3

7、6，46，共有11个元素，已知散列函数为：H（k） = k MOD 11，采用线性探测法处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。5、 已知序列35，29，22，16，17，9，38，27，13，45，请给出采用希尔排序法对该序列做非递减排序时的每一趟结果，增量序列为5，3，1。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的入队操作算法。#define Max_Queue_Size 100Void Insert_CirQueue(SqQueue Q , ElemType e) if

8、 ( ) printf(“The Circular Queue is Overflow!”) ;else ; Q.Queue_arrayQ.rear=e ; 2、 二叉树先序遍历的非递归算法。#define Max_Node_Num 50Void PreorderTraverse( BTNode *T) BTNode *StackMax_Node_Num ,*p=T, *q ; int top=0 ; if (T=NULL) printf(“The Binary Tree is Empty!n”) ; else do visit( p-> data ) ; q=p->Rchild

9、; if ( q!=NULL ) stack+top=q ; ; if (p=NULL) ; while ( ) ; 3、 用正邻接链表保存有向图，各结点的结构形式如下，所有的顶点结点放在数组adjlist中，统计图中顶点的入度。链表结点adjvexinfonextarc顶点结点indegreedatafirstarcVoid count_indegree(ALGraph *G) int k ; LinkNode *p ;for (k=0; k<G->vexnum; k+)G->adjlistk.indegree=0 ;for (k=0; k<G->vexnum;

10、 k+) ;while (p!=NULL) G->adjlistp->adjvex.indegree+ ; ; 4、 冒泡排序算法。#define FALSE 0#define TRUE 1Void Bubble_Sort(Sqlist *L) int j ,k ,flag ;for (j=0; j<L->length; j+) ;for (k=1; k<=L->length-j; k+) /* 一趟排序 */if ( ) flag=FALSE ; L->R0=L->Rk ; L->Rk=L->Rk+1 ; ; if (flag=TR

11、UE) break ; 五、编写算法（要求给出相应的数据结构说明，14分）设以L为头结点的单链表中的所有结点的值均互不相同。对该单链表进行动态查找，查找值为k的结点：若链表中有该值的结点，则删除；若链表中没有该值的结点，则插入为第一个结点；并对算法进行分析。10数据结构模拟试题13参考答案一、填空题（每小题2分，共18分）1、 线性结构 树形结构 图（或网）状结构2、 表的一端 表的另一端3、 数据元素是一个字符4、 2005、 2h-16、 n 2e7、 以顺序方式存储 结点按关键字有序8、 索引 散列9、 归并 内、外存之间的数据交换二、单项选择题（请将答案写在题目后的括号中。每题2分，共

12、18分）题号123456789答案ACBCDBCDA三、分析题（每题6分，共30分）1、 解：依题意对应的Huffman树如下图所示。39891772354691322WPL=(2+3)×4+(4+6+7)×3+(8+9)×2=1052、 解：该网的邻接链表如下图所示： 012312342123748112364112617451821135从顶点V3出发的深度优先搜索的顶点序列是3214，相应的生成树如下：最小生成树1243567从顶点V3出发深度优先搜索生成树124381263、 解：将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入

13、到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除13之后的二叉排序树T1如图(b)所示；最后再插入13之后的二叉排序树T2。图(a) 生成的二叉排序树14719913416251218图(b) 删除13的二叉排序树147199124162518图(c) 插入13的二叉排序树147199124162518134、 解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：H(31)=31 MOD 11=9 H(25)=25 MOD 11=3 H(18)=18 MOD 11=7H(19)=19 MOD 11=8 H(42)=42 MOD 11=9 冲突 H(42)=(9+1) M

14、OD 11=10H(67)=67 MOD 11=1 H(15)=15 MOD 11=4 H(33)=33 MOD 11=0H(17)=17 MOD 11=6 H(36)=36 MOD 11=3 冲突 H(36)=(3+1) MOD 11=4 冲突H(36)=(4+1) MOD 11=5 H(46)=46 MOD 11=2得到的散列表结构如下：散列地址关键字0 1 2 3 4 5 6 7 8 9 1033 67 46 25 15 36 17 18 19 31 42成功查找的平均查找长度：ASL=(1×9+1×2+1×3)/11=14/115、 解：做非递减排序时的每

15、一趟结果如下：初始关键字：35，29，22，16，17，9，38，27，13，45第一趟： 9，29，22，13，17，35，38，27，16，45第二趟： 9，17，16，13，27，22，38，29，35，45第三趟： 9， 13，16，17，22，27，29，35，38，45第三趟归并完毕，排序结束。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的入队操作算法。(Q.rear+1)%Max_Queue_Size=Q.frontQ.rear=(Q.rear+1)%Max_Queue_Size ;2、 二叉

16、树先序遍历的非递归算法。P=p->Lchildp=stacktop-p!=NULL 3、统计图中顶点的入度。P=G->adjlistk.firstarcP=p->nextarc4、冒泡排序算法。flag=TRUEL->Rk.key>L->Rk+1.keyL->Rk+1=L->R0五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定义及算法如下：#define int ElemType typedef struct Lnode ElemType data; /* 数据域，保存结点的值 */struct LNode *next; /* 指针域 */LNode; /* 结点的类型 */void Dynomic_search(LNode *L , ElemType k) LNode *ptr , *p=L, *q=L->next ;while ( q!=NULL&&q->data!=k