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

1、数据结构模拟试题16一、填空题（每小题2分，共20分）1、 数据及其联系在计算机内存中的存储称为数据的物理（存储）结构，基本的物理结构有 和 。2、 数据结构中评价算法的两个重要指标是 和 。3、 堆栈是操作受限的线性结构，只能在 插入和删除元素；不能进行插入和删除元素的一端称为 。4、 有一个10阶对称矩阵A，采用压缩存储方式（以行为主存储），A00的地址是100，若每个元素占3个基本存储单元，则A58的地址是 。5、 设有一棵深度为n的二叉树，它至少有 个结点，至多 有 个结点。6、 动态存储管理主要是解决系统如何 _、_ 的两大问题。7、对线性表进行二分查找时，要求线性表必须是 ，且要求

2、 。8、 对于内部排序，有多种排序方法。按排序基本思想（策略），可分为 、 、 、归并排序和基数排序。9、 索引表是存储记录的 和记录的 之间的对照表，每个元素称为一个索引项。10、 对于文件，按物理结构划分，可分为顺序文件、 文件、 文件和多关键字文件。二、单项选择题（请将答案写在题目后的括号中。每题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、线性表若采用链式存储结

3、构时，要求内存中可用存储单元的地址是（ ）。（A） 必须是连续的 （B） 部分地址必须是连续的（C） 一定是不连续的 （D） 是否连续没有要求3、 判断一个循环队列Q（最多元素个数为m）为满队列的条件是（ ）。（A） Q.front=Q.rear ； （B） Q.front!=Q.rear ；（C） Q.front=(Q.rear+1)%m； （D） Q.front!=(Q.rear+1)%m；4、一棵二叉树，其先序遍历序列是abdehicfg，中序遍历序列是dbheiafcg，则其后序遍历序列是( )。（A） dhiebafgc （B） dhiebfgca（C） dhiebfgac （D）

4、dbhiefgca5、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍，所有顶点的度之和等于所有顶点的入度之和的 倍。（ ）（A） 1/2，1 （B） 2，1 （C） 1，2 （D） 1，46、对于有n个顶点e(e>n)条边的带权无向图，以下关于该图的最小生成树的描述正确的是（ ）。（A） 最小生成树是唯一的。（B） 最小生成树中所有边上的权值之和是唯一的。（C） 最小生成树有n条边。（D） 最小生成树有n个顶点e-1条边。7、 设哈希表长m=14，H（key）=key MOD 13，address(19)=6，address(41)=2，address(57)=5，ad

5、dress(85)=7，其余地址为空。对于关键字31，若用线性探测法解决冲突，其地址是 ；若用二次探测法解决冲突，其地址是 。（ ）（A） 8，4 （B） 11，4 （C） 4，8 （D） 4，118、从未排序序列中挑选元素，并将其依次放入到已排序序列中(初始时为空)的一端的方法是（ ）。（A） 直接插入排序 （B） 选择排序 （C） 快速排序 （D） 堆排序9、 若以3, 5, 6, 8, 14作为叶子的权值构造Huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)，则其带权路径长度WPL为（ ）。（A） 78 （B） 80 （C） 82 （D） 84三、分析题（每题6分，

6、共30分）1、 设QU0，5是一个静态循环队列，初始状态是front=rear=0，画出进行下列操作后队列的头、尾指针的状态变化情况，若不能入队，请指出不能入队的元素，并说明理由。（1） a，e，b入队； （2） a，e出队； （3） s，t，k，m入队； （4） b，s，t出队； （5） r，p，u，v入队；2、 设有一棵树如下图， 给出该树的孩子表示法的复合链表存储结构； 将此树转换为二叉树； 给出转换后二叉树的后序遍历序列。ABDGECHJIF3、 设有如下带权有向无环图， 给出该图的正邻接链表存储结构； 给出对该图进行拓扑排序过程。 9V45107863543V0V1V2V3V54、

7、线性表的关键字集合31，25，18，29，42，69，95，53，17，16，47，116，87，共有13个元素，已知散列函数为：H（k） = k MOD 11，采用链地址法处理冲突，请给出对应的散列表结构。5、 已知关键字序列15，29，12，40，47，39，58，27，73，44，86，55，请给出采用希尔排序法对该序列做非递减排序的过程（设增量序列是5，3，1）。四、算法填空（每空2分，共20分）请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。1、设有一个以L为头结点的双向循环链表，删除数据为key的所有结点，数据结构定义如下：typedef struct L

8、node ElemType key ; /* 关键字码 */struct Lnode *prior; /* 指向直接前趋结点的指针域 */struct Lnode *next; /* 指向直接后继结点的指针域 */LNode; /* 结点的类型 */void *Delete_Node(LNode L，ElemType key) ElemType data; LNode *p;if ( L->next=L) printf(“%s”,” 链表为空！n”); else p=L->next ;while ( ) if (EQ(p->data=key) ) ； ; free(p); /

9、* 删除数据为key的结点 */ 2、非递归中序遍历二叉树。#define MAXNODE 50void InorderTraverse( BTNode *T) BTNode *stackMAXNODE ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do while (p!=NULL) ; p=p->Lchild ; if (top=0) bool=0 ; else p=stacktop ; top- ; visit( p->data ) ; ; while(boo

10、l!=0) ; 以下2题是查找和排序，所使用的记录类型的定义如下：#define MAX_SIZE 100typedef int KeyType ;typedef struct RecType KeyType key ; /* 关键字码 */infoType otherinfo ; /* 其他域 */RecType ;typedef struct Sqlist RecType RMAX_SIZE ; /* 顺序表 */int length ; /* 实际元素个数 */Sqlist ;3、二叉排序树的查找BSTNode *BST_Serach(BSTNode *T , KeyType key)

11、BSTNode *p=T ;while (p!=NULL&& !EQ(p->key, key) ) if ( LT(key, p->key) ) ;else p=p->Rchild ;if (EQ(p->key, key) ) return(p) ;else ;4、选择排序算法void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1; ; m+) k=m ; for (n=m+1; n<=L->length; n+) if ( LT(L->Rn.key, L->Rk.k

12、ey) ) k=n ;if ( ) /* 记录交换 */ L->R0=L->Rm; L->Rm=L->Rk; ; 五、编写算法（12分）设T是指向二叉树根结点的指针变量，每个结点的数据都是字符。 写出输出树中度为1及度为0的结点数的算法。（6分） 写出从根结点开始按层次次序“自上而下，从左至右”输出树中的各结点的算法。（6分）提示：为保证是按层次遍历，必须设置一个队列，初始化时为空。共9页 第13页数据结构模拟试题16参考答案一、填空题（每小题2分，共20分）1、 顺序存储结构 链式存储结构 2、 时间复杂度 空间复杂度3、 栈顶 栈底4、 2745、 n 2n-1 6

13、、 存储空间的分配 释放的存储空间的回收7、 以顺序方式存储 结点按关键字有序8、 插入排序 交换排序 选择排序9、 关键字 存储地址 或 存储地址 关键字10、索引文件 散列(哈希)文件二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案ADCBCDABB三、分析题（每题6分，共30分）102435frontrear(a) 队列初始化 a, e, b入队10243frontrearaeb51、解：做完下列操作后队列的头尾指针的状态变化情况如下面图形所示。 b，s，t出队 r，p，u，v入队10243rearfrontmvp5ukr a, e出队 s，t，

14、k，m入队10243frontm5kreart10243rear5bfront10243frontmtb5skreart每图1分2、解： 该树的孩子表示法的复合链表存储结构如下图；(3分) A BC DE F G H I J 0100 123456789MAX_NODE-1rootnum3 2 1 6 5 4 9 8 7 将此树转换为二叉树如下图。(2分) ABFCEDIJHG 转换后二叉树的后序遍历序列是：GFEJIHDCBA (1分)3、 解： 该图的正邻接链表如下图所示：(2分)V0 2V1 2V2 3V3 1V4 2V5 2 0123451 5 2 3 2 6 4 3 5 5 3 4

15、5 10 4 8 3 9 5 7 给出对该图进行拓扑排序过程如下(3分)，其拓扑序列是：V0V1V2V4V3V5 (1分)9V451078634V1V2V3V59V4510784V2V3V5 输出V0后 输出V1后9V457V3V5 输出V2后5V3V5 输出V4后V5 输出V3后4、 解：根据所给定的散列函数和处理冲突方法，得到的散列表结构如下：01234567891025186917 16 116 87 3129 47 95 4253 5、解：采用希尔排序法对该序列做非递减排序的每一趟结果如下。(一趟3分，二趟2分，三趟1分)444715 29 12 40 47 39 58 27 73 4

16、4 86 55初始关键字：555873558442927554715 29 12 40 44 39 55 27 73 47 86 58一趟排序后：15 27 12 40 29 39 47 44 58 55 86 73二趟排序后：12 15 27 29 39 40 44 47 55 58 73 86三趟排序后：四、算法填空（每空2分，共20分）请在下面各算法的空白处填上相应语句实现算法功能。每个空白处只能填一个语句。1、设有一个以L为头结点的双向循环链表，删除数据为key的所有结点。p>next !=Lp>prior->next=p>nextp->next->

17、prior=p->prior2、非递归中序遍历二叉树。stack+top=pp=p->Rchild3、二叉排序树的查找。p=p>Lchild return(NULL)4、选择排序算法。m<L->length k!=m L->Rk=L->R0五、编写算法（12分）解： 输出树中度为1及度为0的结点数的算法。（6分）#define MAXNODE 50void count_nodes( BTNode *T) BTNode *StackMAXNODE ,*p=T;int top=0, num1=0, num0=0 ;if (T=NULL) printf(“B

18、inary Tree is Empty!n”) ;else stack+top=p ; while (top>0) （循环及控制1分） p=stacktop- ; if ( !(p->Lchild!=NULL&&p->Rchild!=NULL) ) （判断部分3分） if (p->Lchild=NULL&&p->Rchild=NULL) num0+ ; else if (p->Lchild!=NULL|p->Rchild!=NULL) num1+ ; if (p->Rchild!=NULL ) stack+top=p->Rc