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

1、数据结构模拟试题12一、填空题（每小题2分，共18分）1、 数据的逻辑结构包括 ， 和 三种结构。2、 算法分析的两个主要方面是 和 。3、 在双向链表中，每个结点有两个指针域，一个指向 ，另一个指向 。4、 空串是 ，其长度等于 。5、 有一个10阶对称矩阵A，采用压缩存储方式，以行为主存储下三角形到一个一维数组中，若A00的地址是200（每个元素占2个基本存储单元），则A95的地址是 。6、 在非空二叉树的中序遍历序列中，根结点的右边 。7、 采用邻接链表存储图，则图的深度优先搜索算法类似于二叉树的 。8、 在分块查找方法中，首先查找 ，然后再查找相应的 。9、 对于文件，按其记录的类型可

2、将文件分为 文件、 文件。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、有如下递归函数fact(n)，其时间复杂度是（ ）。Fact(int n) if (n<=1) return 1; else return(n*fact(n-1) ;（A） O(n) （B） O(n2) （C） O(2n) （D） O(n2n)2、 设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则向S中压入一个元素P执行的操作是（ ）。（A） Stop+=p； （B） S+top=p；(C) S-top=p； （D） Stop-=p； 3、 稀疏矩阵一般的压缩存储方法有主要有（ ）两

3、种。（A） 二维数组和三维数组 （B） 三元组和散列（C） 三元组和十字链表 （D） 散列和十字链表4、 一般树的存储结构主要有（ ）。（A） 双亲表示法，孩子表示法，链表表示法（B） 双亲表示法，孩子表示法，孩子兄弟表示法（C） 双亲表示法，孩子兄弟表示法，链表表示法（D） 双亲表示法，孩子兄弟表示法，链表表示法5、 一棵有n(n0)个结点的满二叉树的叶子结点的数目是 ，非叶子结点的数目是 。（ ）（A） 22n 22n （B） 22n-1 22n （C） 22n-1 22n-1 （D） 22n 22n-16、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍，所有顶点的度之和

4、等于所有顶点的入度之和的 倍。（ ）（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，47、设有一个长度为12的有序表，采用二分查找方法对该表进行查找时，在表内各元素等概率情况下查找成功所需的平均比较次数为。（ ）(A) 35/12 （B） 37/12 （C） 39/12 （D） 43/128、 设有一组记录的关键字是（37，28，56，80，60，14，25，50），用快速排序法以第一个记录为基准得到的一次划分结果是（ ）。（A） 25，28，37，14，56，80，60，50 （B） 25，28，37，14，60，80，56，50 （C） 25，28，14，37，60，80，

5、56，50 （D） 25，28，14，37，60，56，80，509、 文件在外存上的上的组织方式称为文件的物理结构。基本的物理结构有：（ ）(A) 顺序结构，链接结构，线性结构 (B) 线性结构，链接结构，索引结构(C) 顺序结构，链接结构，线性结构 (D) 顺序结构，链接结构，索引结构三、分析题（每题6分，共30分）1、 设有一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，请画出这棵二叉树，然后画出其后序线索化树。2、 对于下图中的网，写出该网的邻接链表；然后写出其广度优先搜索生成树（假设从顶点V1出发）；最后给出按Prime算法从顶点V5出发得到的最小生

6、成树。1524389113341373、 将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除18之后的二叉排序树T1；最后再画出插入18之后的二叉排序树T2。4、 线性表的关键字集合71，25，8，29，42，69，95，33，17，56，47，共有11个元素，已知散列函数为：H（k） = k MOD 11，采用链地址处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。5、 已知序列35，29，52，60，17，9，38，27，13，45，请给出采用归并排序法对该序列做非递减排序时的每一趟结果。四、算法

7、填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的队首元素出队操作算法。#define Max_Queue_Size 100ElemType Delete_CirQueue(SqQueue Q) ElemType x ; if ( ) printf(“The Circular Queue is Null!”) ;else x=Q.Queue_arrayQ.front ; ; 2、 二叉树中序遍历的非递归算法。#define Max_Node_Num 50Void InorderTraverse( BTNode *T)

8、BTNode *StackMax_Node_Num ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“The Binary Tree is Empty!n”) ; else do while (p!=NULL) stack+top=p ; p=p->Lchild ; if (top=0) bool=0 ; else ; visit( p->data ) ; ; while ( ) ; 3、 折半查找算法。int Bin_Search(SSTable ST , KeyType key) int Low=1，High=ST.length,

9、 Mid ; while (Low<High) ; if (ST. elemMid.key=key) return(Mid) ; else if (ST. elemMid.key<key) Low=Mid+1 ;else High=Mid-1 ; ; 4、 简单选择排序算法。void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1;m<L->length;m+) k=m ; for (n=m+1;n<=L->length;n+) if ( ) k=n ; if ( ) L->R0=L->

10、;Rm; L->Rm=L->Rk; ; 五、编写算法（要求给出相应的数据结构说明，14分）将以L为头结点的单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同；并对算法进行分析。10数据结构模拟试题12参考答案一、填空题（每小题2分，共18分）1、 线性结构 树形结构 图（或网）状结构2、 时间复杂度 空间复杂度3、 (直接)前驱结点 (直接)后继结点4、 零个字符组成的串 0 5、 3006、 只有右子树上的所有结点7、 先序遍历8、 索引 块9、 操作系统 数据库二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案ABCBDBB

11、CD三、分析题（每题6分，共30分）fabcehidgNULLfabcehidg图(a) 二叉树图(b) 后序线索化树1、 解：所画出的二叉树如图(a)所示。树的后序遍历序列是gdhiebfca，其后序线索化树如图(b)所示。2、 解：该网的邻接链表如下图所示：0123412345293758193441351124174321333532114318从顶点V1出发的广度优先搜索的顶点序列是12354，相应的生成树如下：1524389137从顶点V1出发广度优先搜索生成树从顶点V5出发的最小生成树1524333473、 解：将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到

12、初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除18之后的二叉排序树T1如图(b)所示；最后再插入18之后的二叉排序树T2。149197134256图(b) 删除18的二叉排序树14918713419256图(a) 生成的二叉排序树14919713418256图(c) 插入18后的二叉排序树4、 解：根据所给定的散列函数和处理冲突方法，得到的散列表结构如下：0123456789103356 25477117 298 4295 69成功查找的平均查找长度：ASL=(1×8+2×2+3×1)/11=17/115、 解：做非递减排序时的每一趟结果如下：初始

13、关键字：35，29，52，60，17，9，38，27，13，45第一趟： 29，35 52，60 9，17 27，38 13，45第二趟： 29，35，52，60 9，17，27，38 13，45第三趟： 29，35，52，60 9，13，17，27，38，45第四趟： 9，13，17，27，29，35，38，45，52，60第四趟归并完毕，排序结束。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的队首元素出队操作算法。Q.front=Q.rearQ.front=(Q.front+1)%Max_Queue_S

14、ize ;2、 二叉树中序遍历的非递归算法。p=stacktop-p=p->Rchildbool!=0 3、 折半查找算法。Mid=(Low+High)/2return(0)4、 简单选择排序算法。L->Rn.key<L->Rk.keyk!=mL->Rk=L->R0五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定义及算法如下：#define int ElemType typedef struct Lnode ElemType data; /* 数据域，保存结点的值 */struct LNode *next; /* 指针域 */LNode; /* 结点的类型 */void Delete_LinkList_Value(LNode *L) LNode *p=L->next, *q, *ptr ;ElemType k ;while ( p->next!=NULL) k=p->data ; ptr=p ; q=ptr->next ;while (q!=NULL) if (q->data=k) ptr->next=q->next