07-11杭电851数据结构真题

5、算法设计题：一个线性表中的元素为正整 数或负整数。设计一个算法，将正整数和 负整数分开，使线性表前一半为负整数， 后一半为正整数。不要求对这些元素排序， 但要求尽量减少交换次数。
5、参考答案： 本题的算法思想是：先设置好上、下界，然后分别从线性表两端查找 正数和负数，找到后进行交换，直到上、下界相遇。 void example ( datatype A [n] ) { i = 1, j = n ; /* i , j为左右边界 */ while ( i < j ) { while ( ( i < j ) && ( A[ i ] < 0 ) ) i++ ; /* 在左边界找正数 */ while ( (i < j ) && ( A[ j ] > 0 )) j - - ; /* 在右边界找负数 */ if ( i < j) { temp = A[ i ]; A[ i ] = A[ j ]; A[ j ] = A [temp ] ; /*交换两个元素 的值 */ i++ ; j - -; } } }
对于有向无环图，写出它的四个不同的拓 扑有序序列。
已知非空二叉树采用顺序存储结构，树中 结点的数据信息依次存放在一个一维数组 中，即 求该二叉树的中序列遍历序列。
1、已知一棵具有n个结点的完全二叉树，自行定 义该树的某种存储方式，根据该存储方式，设计 一个算法，求解给定结点的双亲结点和左右孩子 结点。 2、对于一组数据元素的给定表，根据数据元素在 表中的次序，设计一算法构造一棵二叉排序树 了解更多关于期末考试信息，请关注新浪微博 听刘遵义讲故事 /u/2519554322
现有某二叉树，按先根遍历的序列为 ABDEFCGH，按中根遍历的序列为 DEFBGHCA，试画出此二叉树。

2022年杭州电子科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下述文件中适合于磁带存储的是（）。

A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程3、算法的计算量的大小称为计算的（）。

A.效率B.复杂性C.现实性D.难度4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

杭州电子科技大学2011数据结构期末试卷杭州电子科技大学学生考试卷（ A ）卷考试课程数据结构考试日期 2011 年月日成绩课程号教师号任课教师姓名考生姓名学号（8位）年级专业一．判断题：（每小题2分，共20分）1．链栈的初始化是指开辟足够多的结点，然后置栈顶指针为NULL。

（）2．数据的物理结构是指数据在计算机内的实际存储形式。

（）3．线性表采用链表存储时，查找第i个元素的时间与i的值无关。

（）4．将一棵树转成二叉树，根结点没有左子树。

（）5．广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。

（）6．完全二叉树的某结点若无左孩子，则它必是叶结点。

（）7．用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。

（）8．图的深度优先遍历序列和广度优先遍历序列不是唯一的。

（）9．用简单选择排序算法，只需一趟扫描即可选出键值最大（或最小）的元素。

（）10. 采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。

（）二．选择题：（每小题2分，共18分）1．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A. 13B. 33C. 18D. 402．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．循环队列存储在数组A[0..m]中，则入队时的操作为（）。

A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod mD. rear=(rear+1)mod(m+1)4.对于深度为K的满二叉树(结点编号从1开始，根结点的层数为1)，其第K层上最后1个结点的编号为 ( )。

数据结构试卷（一）一、单选题（每题 2 分，共20分）1.栈和队列的共同特点是( A )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( D ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( D )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

CA．688 B．678 C．692D．6965.树最适合用来表示( C )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( D ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为CA. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（D）个A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：正确性易读性强壮性和_高效率。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___0(n)_____。