《算法与数据结构》模拟试题5

《《算法与数据结构》模拟试题5》由会员分享，可在线阅读，更多相关《《算法与数据结构》模拟试题5（7页珍藏版）》请在金锄头文库上搜索。

1、1算法与数据结构模拟试题 5一、填空题（每小题 2 分，共 18 分）1、 对于给定的 n 个元素,可以构造出的逻辑结构有集合, ，和 四种。2、 数据结构中评价算法的两个重要指标是 和 。3、 顺序存储结构是通过 表示数据元素之间的(逻辑)关系；链式存储结构是通过 表示数据元素之间的(逻辑)关系。4、 栈是 的线性表，其操作数据的基本原则是 。5、 设有一个二维数组 A0909，若每个元素占 5 个基本存储单元，A00 的地址是 1000，若按行优先（以行为主）顺序存储，则 A68的存储地址是 。6、 二叉树由根结点， 和 三个基本单元组成。7、 若采用邻接矩阵存储一个图所需要的存储单元取决

2、于图的 ；无向图的邻接矩阵一定是 。8、 在查找时，若采用折半查找，要求线性表 ，而哈希表的查找，要求线性表 。9、对于文件，按物理结构划分，可分为顺序文件、 文件、文件和多关键字文件。二、单项选择题（请将答案写在题目后的括号中。每题 2 分，共 18 分）1、有如下递归函数 fact(n)，其时间复杂度是（ ） 。Fact(int n) if (nnext=NULL； （B） p=NULL；（C） p-next=head； （D） p=head； 3、设有一个栈顶指针为 top 的顺序栈 S，top 为 0 时表示栈空，则从 S 中取出一个元素保存在 P 中执行的操作是（ ） 。（A） p=

3、Stop+； （B） p=S+top；（C） p=S-top； （D） p=Stop-； 4、 广义表(a, (a, b), d, e, (i, j), k)的长度是 ，深度是 。 （ ）（A） 6，3 （B） 5，3 （C） 6，4 （D） 6，25、 当一棵有 n 个结点的二叉树按层次从上到下，同层次从左到右将(结点)数据存储在一维数组 A1n中时，数组中第 i 个结点的左子结点是 。 （ ）（A） A2i(2in) （B） A2i+1(2i+1n) （C） Ai/2 （D） 条件不充分，无法确定6、设有一棵二叉树，其先序遍历序列是 acdgehibfkj，中序遍历序列是 dgcheiab

4、kfj，则该二叉树的后序遍历序列是 。 （ ）（A） gdehickjfba （B） gdhiecfkjba （C） dghieckjfba （D） gdhieckjfba7、 在一个有向图中，所有顶点的出度之和等于所有顶点的入度之和的 倍，所有顶点的度之和等于所有顶点的出度之和的 倍。 （ ）（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，48、设有一组记录的关键字为19, 14, 23, 1, 68, 20, 84, 27，用链地址法构造哈希表，哈希函数为 H(key)=key MOD 13，哈希地址为 1 的链表中有 个记录。 （ ）(A) 4 （B ） 2 （C） 3

5、（D ） 19、 用直接插入法对下列四个序列按非递减方式排序，元素比较次数最少的是（ ） 。3（A） 21，32， 46，40，80，69，90，94 （B） 94，32，40，90，80，46，21，69 （C） 32，40，21，46，69，94，90，80 （D ） 90，69，80，46，21，32，94，40三、分析题（每题 6 分，共 30 分）1、 若以7, 19, 2, 6, 32, 3, 21, 10作为叶子结点的权值，请构造对应的 Huffman 树，然后求出其带权路径长度 WPL。2、 对于下图中的网，写出该网的邻接链表；然后写出其广度优先搜索生成树（假设从顶点 V1出发

6、） ；最后给出按 Kruskal 算法得到的最小生成树。3、 将关键字序列（15，21，13，7，4，9，25，19，23）插入到初态为空的二叉排序树15 24 36 8113341074中，请画出建立二叉排序树 T 的过程；然后画出删除 13 之后的二叉排序树 T1。4、 线性表的关键字集合71，25，8，29，42， 69，95，33，17，56，47，共有 11 个元素，已知散列函数为：H（k） = k MOD 11，采用链地址处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。5、 已知序列15，29，13，40，17，9，38，27，52，45 ，请给出采用增量序列为

7、 5, 3, 1 的希尔排序法，对该序列做非递减排序时的每一趟结果。四、算法填空（每空 2 分，共 20 分）5请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。1、头插入法创建单链表，以整数的最大值(32767)作为输入结束，链表的头结点 head 作为返回值。LNode *create_LinkList(void) int data; LNode *head, *p ;head= (LNode *)malloc(sizeof(LNode) ; head-next=NULL; /*创建链表的表头结点 head*/ while (1) scanf(“%d”,& data

8、) ;if (data=32767) break ;；pdata=data; ；headnext=p ; return (head); 2、按满二叉树的方式对结点进行编号建立链式二叉树。对每个结点，输入结点 i、结点 ch。#define Max_Node_Num 50Typedef struct BTNode char data ;struct BTNode *Lchild , *Rchild ;BTNode ;6BTNode *Create_BTree() BTNode *T , *p , *sMax_Node_Num ; char ch ; int i , j ;while (1) sc

9、anf(“%d”,&i) ;if (i=0) break ; /*以编号 0 作为输入结束*/else ch=getchar() ;p=(BTNode *)malloc(sizeof(BTNode) ;pdata=ch ;si=p ;if (i=1) T=p ; else j=i/2 ; /* j 是 i 的双亲结点编号 */ if ( ) sj-Lchild=p ;else ;return(T) ;3、 图的邻接链表的结点结构如下图所示。下面算法是从顶点 v 出发，递归地深度优先搜索图 G。#define MAX_VEX_NUM 30 /* 最大顶点数 */BOOLEAN VisitedMA

10、X_VEX_NUM ;void DFS(ALGraph *G , int v)data firstarc顶点结点adjvex info nextarc表结点7 LinkNode *p ;Visitedv=TRUE ; Visitv ; /* 置访问标志，访问顶点 v */ ;while (p!=NULL) if (!Visitedp-adjvex) ; 4、 冒泡排序算法。#define FALSE 0#define TRUE 1Void Bubble_Sort(Sqlist *L) int j ,k ,flag ;for (j=0; jlength; j+) /* 共有 n-1 趟排序 */ flag=TRUE ;for (k=1; klength-j; k+) /* 一趟排序 */if ( ) flag=FALSE ; L-R0=L-Rk ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if ( ) break ; 五、编写算法（要求给出相应的数据结构说明，14 分）设 T 是指向二叉树根结点的指针变量，用非递归方法统计树中度为 1 和度为 0 的结点个数。