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

《《算法与数据结构》模拟试题5new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、成。7、若采用邻接矩阵存储一个图所需要的存储单元取决于图的；无向图的邻接矩阵一定是。8、在查找时，若采用折半查找，要求线性表，而哈希表的查找，要求线性表。9、对于文件，按物理结构划分，可分为顺序文件、文件、文件和多关键字文件。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、有如下递归函数fact(n)，其时间复杂度是（）。Fact(intn){if(n<=1)return1;elsereturn(n*fact(n-1));}7（A）O(n)（B）O(n2)（C）O(㏒2n)（D）O(n㏒2n

3、)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

4、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）gdhieckjfba7、在一个有向图中，所有顶点

5、的出度之和等于所有顶点的入度之和的倍，所有顶点的度之和等于所有顶点的出度之和的倍。（）（A）1/2，1（B）1，2（C）2，1（D）1，48、设有一组记录的关键字为{19,14,23,1,68,20,84,27}，用链地址法构造哈希表，哈希函数为H(key)=keyMOD13，哈希地址为1的链表中有个记录。（）(A)4（B）2（C）3（D）19、用直接插入法对下列四个序列按非递减方式排序，元素比较次数最少的是（）。（A）21，32，46，40，80，69，90，94（B）94，32，40，90，80，46，21

6、，69（C）32，40，21，46，69，94，90，80（D）90，69，80，46，21，32，94，407三、分析题（每题6分，共30分）1、若以{7,19,2,6,32,3,21,10}作为叶子结点的权值，请构造对应的Huffman树，然后求出其带权路径长度WPL。2、对于下图中的网，写出该网的邻接链表；然后写出其广度优先搜索生成树（假设从顶点V1出发）；最后给出按Kruskal算法得到的最小生成树。1524368113341073、将关键字序列（15，21，13，7，4，9，25，19，23）插入到初

7、态为空的二叉排序树中，请画出建立二叉排序树T的过程；然后画出删除13之后的二叉排序树T1。74、线性表的关键字集合{71，25，8，29，42，69，95，33，17，56，47}，共有11个元素，已知散列函数为：H（k）=kMOD11，采用链地址处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。5、已知序列{15，29，13，40，17，9，38，27，52，45}，请给出采用增量序列为5,3,1的希尔排序法，对该序列做非递减排序时的每一趟结果。四、算法填空（每空2分，共20分）请在下面各算

8、法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。1、头插入法创建单链表，以整数的最大值(32767)作为输入结束，链表的头结点head作为返回值。7LNode*create_LinkList(void){intdata;LNode*head,*p;head=(LNode*)malloc(sizeof(LNode));head->next=NULL;/*创建链表的表头结点h