《算法与数据结构》考试试卷

《《算法与数据结构》考试试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、姓名:学号:系别:年级专业:(密封线内不答题)……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………东莞理工学院（本科）试卷（A卷）2009-2010学年第二学期《算法与数据结构》试卷（A卷）一、填空题（每小题2分，共18分）1、对于给定的n个元素,可以构造出的逻辑结构有集合,，和四种。2、数据结构中评价算法的两个重要指标是和。3、在顺序存储结构中，逻辑上相邻的数据元素，其物理位置，在单链表中，逻辑

2、上相邻的数据元素，其物理位置。4、栈是操作受限的线性表，其操作数据的基本原则是，允许进行插入和删除操作的一端称为。5、设有一个二维数组A[10][10]，若每个元素占6个基本存储单元，A[0][0]的地址是1000，若按行优先（以行为主）顺序存储，则元素A[6][8]的存储地址是；若按列优先（以列为主）顺序存储，则元素A[6][8]的存储地址是。6、设有一棵深度为n的完全二叉树，该二叉树至少有个结点，至多有个结点。7、若采用邻接矩阵存储一个图所需要的存储单元取决于图的；无向图的邻接矩阵一定是。8、在进行排序时，最基

3、本的操作是和。9、在查找时，若采用折半查找，要求线性表，而哈希表的查找，要求线性表。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、设有长度为n的数组a,假设已经赋值，下面程序段的时间复杂度是（）。for(i=0;ia[j])k=j;if(k!=i){temp=a[i];a[i]=a[k];a[k]=temp;}共8页，第7页}（A）O(n)（B）O(n2)（C）O(㏒2n)（D）O(n㏒2n)2、设有以head为头

4、结点的非空单循环链表，链表中只有一个结点条件是（）。（A）head->next=head；（B）head->next=head->next；（C）head->next->next=head；（D）head->next->next=head->next；3、设有一个大小为Max的循环队列Q，判断该队列为满的条件是（）。（A）Q.rear-Q.front==Max（B）Q.rear-Q.front-1==Max（C）Q.rear==Q.front（D）(Q.rear+1)%Max==Q.front4、二叉树是非线性结构

5、，因此（）（A）不能用顺序存储结构存储（B）不能用链式存储结构存储（C）既能用链式存储结构存储，也能用顺序存储结构存储（D）既不能用链式存储结构存储，也不能用顺序存储结构存储5、设有一棵二叉树，其先序遍历序列是acdgehibfkj，中序遍历序列是dgcheiabkfj，则该二叉树的后序遍历序列是（）。（A）gdehickjfba（B）gdhiecfkjba（C）dghieckjfba（D）gdhieckjfba6、在一个有向图中，所有顶点的出度之和等于所有顶点的入度之和的倍，所有顶点的度之和等于所有顶点的出度之和

6、的倍。（）（A）1/2，1（B）1，2（C）2，1（D）1，47、对于有n个顶点e(e>n)条边的带权无向图，以下关于该图的最小生成树的描述正确的是（）。姓名:学号:系别:年级专业:(密封线内不答题)……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………（A）最小生成树是唯一的。（B）最小生成树中所有边上的权值之和是唯一的。（C）最小生成树有n条边。（D）最小生成树有n个顶点e-1条边。8、设有关键

7、集合{21，12，46，40，32，29，65，53}，采用冒泡排序法进行一趟排序操作后的结果是（）。（A）12，21，46，40，32，29，53，65（B）12，21，40，46，32，29，53，65（C）12，21，40，32，46，29，53，65（D）12，21，40，32，29，46，53，65共8页，第7页9、设有一组记录的关键字为{19,41,23,38,28,54,84,27}，用链地址法构造哈希表，哈希函数为H(key)=keyMOD13，哈希地址为2的链表中有个记录。（）(A)3（B）4（C

8、）2（D）1三、分析题（每题6分，共30分）1、设有一棵树，采用双亲表示法的存储结构如右图，请解决以下问题：01234567891011A-1B0C0D0E1F1G2H2I2J3K4M4①画出该树的逻辑结构（2分）②给出对该树进行先序遍历的遍历序列（1分）③画出将该树转换的二叉树（2分）④给出对转换后的二叉树的后序遍历序列（1分）2、对于下图中的带权无向图，