《算法与数据结构》模拟试题5
一、填空题（每小题2分，共18分）
1、 对于给定的n个元素,可以构造出的逻辑结构有集合, ，
和 四种。
2、 数据结构中评价算法的两个重要指标是 和 。
3、 顺序存储结构是通过 表示数据元素之间的(逻辑)关系；链式存储结构是通过 表示数据元素之间的(逻辑)关系。
4、 栈是 的线性表，其操作数据的基本原则是 。
5、数据结构与算法分析答案 设有一个二维数组A[0…9][0…9]，若每个元素占5个基本存储单元，A[0][0]的地址是1000，若按行优先（以行为主）顺序存储，则A[6][8]的存储地址是 。
6、 二叉树由根结点， 和 三个基本单元组成。
7、 若采用邻接矩阵存储一个图所需要的存储单元取决于图的 ；无向图的邻接矩阵一定是 。
8、 在查时，若采用折半查，要求线性表 ，而哈希表的查，要求线性表 。
9、对于文件，按物理结构划分，可分为顺序文件、 文件、
文件和多关键字文件。
二、单项选择题（请将答案写在题目后的括号中。每题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(n㏒2n)
2、 以head为头结点的非空单循环链表的尾结点p的特点是（ ）。
（A） p->next=NULL； （B） p=NULL；
（C） p->next=head； （D） p=head；
3、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则从S中取出一个元素保存在P中执行的操作是（ ）。
（A） p=S[top++]； （B） p=S[++top]；
（C） p=S[--top]； （D） p=S[top--]；
4、 广义表(a, (a, b), d, e, ((i, j), k))的长度是 ，深度是 。（ ）
（A） 6，3 （B） 5，3 （C） 6，4 （D） 6，2
5、 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将(结点)数据存储在一维数组A[1…n]中时，数组中第i个结点的左子结点是 。（ ）
（A） A[2i](2i≤n) （B） A[2i+1](2i+1≤n)
（C） A[i/2] （D） 条件不充分，无法确定
6、设有一棵二叉树，其先序遍历序列是acdgehibfkj，中序遍历序列是dgcheiabkfj，则该二叉树的后序遍历序列是 。（ ）
（A） gdehickjfba （B） gdhiecfkjba
（C） dghieckjfba （D） gdhieckjfba
7、 在一个有向图中，所有顶点的出度之和等于所有顶点的入度之和的 倍，
所有顶点的度之和等于所有顶点的出度之和的 倍。（ ）
（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，4
8、设有一组记录的关键字为{19, 14, 23, 1, 68, 20, 84, 27}，用链地址法构造哈希表，哈希函数为H(key)=key MOD 13，哈希地址为1的链表中有 个记录。（ ）
(A) 4 （B） 2 （C） 3 （D） 1
9、 用直接插入法对下列四个序列按非递减方式排序，元素比较次数最少的是（ ）。
（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出发）；最后给出按Kruskal算法得到的最小生成树。
3、 将关键字序列（15，21，13，7，4，9，25，19，23）插入到初态为空的二叉排序树中，请画出建立二叉排序树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}，请给出采用增量序列为5, 3, 1的希尔排序法，对该序列做非递减排序时的每一趟结果。
四、算法填空（每空2分，共20分）
请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。
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) ;
if (data==32767) break ;
；
p–>data=data;
；
head–>next=p ;
}
return (head);
}
2、按满二叉树的方式对结点进行编号建立链式二叉树。对每个结点，输入结点i、结点ch。
#define Max_Node_Num 50
Typedef struct BTNode
{ char data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ;
BTNode *Create_BTree()
{ BTNode *T , *p , *s[Max_Node_Num] ;
char ch ; int i , j ;
while (1)
{ scanf(“%d”,&i) ;
if (i==0) break ; /*以编号0作为输入结束*/
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论