当前位置：文档之家 › 哈工大2010春数据结构与算法A卷

哈工大2010春数据结构与算法A卷

  • 格式：pdf
  • 大小：184.95 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

2010黑龙江省数据结构与算法试题及答案

2010黑龙江省数据结构与算法试题及答案

30、数据结构中，在逻辑上可以把数据结构分成（ B ）。
A）动态结构和静态结构
B）线性结构和非线性结构
C）紧凑结构和非紧凑结构
D）内部结构和外部结构
31、数据结构研究的内容是（ D ）。
A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]
C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]
20、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。
38、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ B ）。
A) rear=rear->next; B) front=front->next;
C) rear=front->next; D) front=rear->next ;
A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表
21、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。
A) Head(Head(Tail(Tail(L))))
B) Tail(Head(Head(Tail(L))))
13、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。
A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]
C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]
14、n个顶点的强连通图至少有（ A ）条边。
2、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

2010黑龙江省数据结构考试高级

2010黑龙江省数据结构考试高级
ቤተ መጻሕፍቲ ባይዱ
2、设 T 是一棵满二叉树，编写一个将 T 的先序遍历序列转换为后序遍历序列的递归算法。 3、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表 头指针为 head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表 指针。分析你的算法的时、空复杂度。 4、在有向图 G 中，如果 r 到 G 中的每个结点都有路径可达，则称结点 r 为 G 的根结点。编写 一个算法完成下列功能： （1） ．建立有向图 G 的邻接表存储结构； （2） ．判断有向图 G 是否有根，若有，则打印出所有根结点的值。 5、 由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树， 下面程序的作用是实现由 已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序 遍历序列，请写出程序所缺的语句。 #define MAX 100 typedef struct Node {char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv) { TNODE *root; if(argc<3) exit 0; strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); } TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; if(n<=0) return NULL; ptr->info=(1)_______; for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break; k=(3)_______; ptr->llink=restore(ppos+1, (4)_______,k ); ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; } postorder(TNODE*ptr) { if(ptr=NULL) return; postorder(ptr->llink); postorder(ptr->rlink); } int k;

数据结构(代码02331)2010年10月试题及答案

数据结构(代码02331)2010年10月试题及答案

全国2010年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.数据的四种存储结构是( ) A-P3A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是( ) D-P26（带尾指针）A.无头结点的单向链表B.带头结点的单向链表C.带头结点的双循环链表D.带头结点的单循环链表3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( )C P22A.head=NULLB.head->next=NULLC.head!=NULLD.head->next!=head4.若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是( )DA.n-iB.n-i+lC.n-i+2D.无法确定5.串匹配算法的本质是( ) C P55A.串复制B.串比较C.子串定位D.子串链接6.设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为( ) C P61A.13B.18C.33D.407.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) BA.树中没有度为2的结点B.树中只有一个根结点C.树中非叶结点均只有左子树D.树中非叶结点均只有右子树8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) AA.nB.C. +1D.n/29.在图G中求两个结点之间的最短路径可以采用的算法是( )A P123A.迪杰斯特拉（Dijkstra）算法B.克鲁斯卡尔（Kruskal）算法C.普里姆(Prim)算法D.广度优先遍历(BFS)算法10.下图G=(V,E)是一个带权连通图，G 的最小生成树的权为( )D P116 A.15 B.16 C.17 D.1811.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) B P108 A.1 2 3 4 5 6 7B.1 4 2 6 3 7 5C.1 4 2 5 3 6 7D.1 2 4 6 5 3 712.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( ) B P136 A.不稳定的 B.稳定的 C.基于交换的D.基于选择的13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为( ) C P198 A.1 B.2 C.3D.414.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( ) D P17415.若需高效地查询多关键字文件，可以采用的文件组织方式为( ) D P218A.顺序文件B.索引文件C.散列文件D.倒排文件二、填空题（本大题共10小题，每小题2分，共20分）请每小题的空格中填上正确答案。

2010年计算机专业统考试题数据结构

2010年计算机专业统考试题数据结构

基本内容
7、线索二叉树 前序：结点x的后继为其左孩子的根，若没有左孩子， 则为右孩子的根，若既无左孩子又无右孩子，后继 为祖先结点的右孩子的根。 中序：结点x的右孩子不为空，后继为其右孩子的根 结点，若右孩子为空，后继为其双亲结点。 后序：若结点x是二叉树的根，后继为空；若结点x是 其双亲的右孩子或是左孩子且双亲没有右孩子，后 继为双亲；若结点x是其双亲的左孩子且双亲有右 孩子，后继为双亲的右孩子中按后序遍历的第一个 结点。
void PostOrder(Bitree T) { Bitree stack[], p; int tag[], top=0; p=T; while(top>0||p!=NULL) { while(p!=NULL) { top++; stack[top]=p; tag[top]=0; p=p->lchild; } if(top>0) { p=stack[top]; while(tag[top]==1) { top--; visit(p->data); p=stack[to} if(top>0) { p=stack[top]; p=p->rchild; tag[top]=1;} } } }
例题
2、交换所有结点的左右子树。 void Bitree_Revolute(Bitree T) { if(T!=NULL) T->lchild<->T->rchild; if(T->lchild) Bitree_Revolute(T->lchild); if(T->rchild) Bitree_Revolute(T->rchild); }
void inorderexp( Bitree bt) { if(bt) { if(bt->lchild!=NULL) { m=precede(bt->data,bt->lchild->data); if(m==1) printf(“(“); inorderexp(bt->lchild); if(m==1) printf(“)”); } printf(bt->data); if(bt->rchild!=NULL) { m=precede(bt->data, bt->rchild->data); if(m==1) printf(“(“); inorderexp(bt->rchild); if(m==1)printf(“)”); } } }

2022年哈尔滨工程大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年哈尔滨工程大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年哈尔滨工程大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.333、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

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

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

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

哈工大 数据结构 2010春A卷 试题

哈工大 数据结构 2010春A卷 试题

哈工大2010年春季学期数据结构与算法 A 试 卷一、填空题（每空1分，共15分） 1. 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是____________。

2．某二叉树的前序遍历序列是ABCDEFG ，中序遍历序列是CBDAFGE ，则其后序遍历序列是_______________。

3．在有n 个叶子的哈夫曼树中，分支结点总数为___________个。

4．对于含有n 个顶点e 条边的连通图，利用Prim 算法求最小生成树的时间复杂度为___________。

5. 表达式a*(b+c)-d 的后缀表达式是___________。

6. 假定一棵二叉树的结点数为18，则它的最小深度为_______，最大深度为______。

7. 设有一个n 阶的下三角矩阵A ，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______ 个数据元素。

8. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。

9. 磁盘文件的归并技术有______________、____________、__________。

10. 设有向图G 中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。

11.设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行________趟的分配和回收才能使得初始关键字序列变成有序序列。

12. 利用Dijkstra 算法求从有向图顶点v1到其他各顶点的最短路径要求边上权值_________。

哈尔滨工程大学数据结构历年试卷试卷1

第2页 共 2页8、一棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有( )个结点。

A ．2hB ．2h-1C ．2h+1D ．h+19、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。

A ．先序B ．中序C ．后序D ．按层次遍历10、一棵二叉树的先序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ ）。

A ．CABDEFGB ．ABCDEFGC ．DACEFBGD ．ADBCFEG11、一棵有n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i 个结点（i 从1开始用上述方法编号）的右孩子在数组A 中的位置是（ ）A ．A[2i](2i<=n)B ．A[2i+1](2i+1<=n)C ．A[i-2]D ．条件不充分，无法确定12、一个n 个顶点的连通无向图，其边的个数至少为（ ）。

A ．n-1B ．nC ．n+1D ．nlogn13、下列关于AOE 网的叙述中，不正确的是（ ）。

A ．关键活动不按期完成就会影响整个工程的完成时间B ．任何一个关键活动提前完成，那么整个工程将会提前完成C ．所有的关键活动提前完成，那么整个工程将会提前完成D ．某些关键活动提前完成，那么整个工程将会提前完成 14、下面关于折半查找的叙述正确的是( )。

A ．表必须有序，表可以顺序方式存储，也可以链表方式存储C ．表必须有序，而且只能从小到大排列B ．表必须有序且表中数据必须是整型，实型或字符型D ．表必须有序，且表只能以顺序方式存储A．直接插入排序B．起泡排序C．快速排序D．直接选择排序二、判断题（每空1分，共10分）1、数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构。

( )2、对任何数据结构，链式存储结构一定优于顺序存储结构。

《数据结构与算法》2010(A)答案解析.

广西工学院 2010 — 2011 学年第 1 学期考试试题考核课程 数据结构与算法 （ A 卷）考核班级 计y091~096 学生数 215 印数 230 考核方式 闭卷 考核时间 120 分钟【说明】试题满分共100分；考试时间为2个小时；一、选择题（每小题2分，共30分）1、设一序列为：1，2，3，4，5，6。

通过栈操作不可能产生的序列为 B 。

A 、3，2，5，6，4，1 B 、1，5，4，6，2，3 C 、2，4，3，5，1，6 D 、4，5，3，6，2，1这题考栈的性质:后进先出。

进栈的序号是1最先6最后，但不规定要同时进，然后再出栈。

可以1进去，1出来，然后2进去，2出来，也可以1进去，2进去，2出来，1出来。

按照这个原则，先看：A ）是可能的，进出栈情况如下：1,2,3依次进栈，3出栈2出栈；4,5进栈，5出栈；6进栈，6出栈；4再出栈，最后是1出栈。

B ）不可能：原因：1进栈1出栈；2,3,4,5进栈，5出栈4出栈；6再进栈，6出栈，此时3在栈顶，2不可能比3还要先出栈。

其他的答案依此可以得出。

2、设有向图G=（V ，E ），V={1，2，3，4，5，6}；E={<1，2>，<2，1>，<6，3>，<2，3>，<5，6>，<2，4>，<3，5>}。

则其强连通分量个数为 A 。

A 、3 B 、4 C 、5 D 、6考有向图中的强联通分量问题：首先要把强联通分量概念弄清楚：有向图强连通分量在有向图G 中，如果两个顶点vi,vj 间（vi<>vj ）有一条从vi 到vj 的有向路径，同时还有一条从vj 到vi 的有向路径，则称两个顶点强连通(strongly connected)。

如果有向图G 的每两个顶点都强连通，称G 是一个强连通图。

非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

哈尔滨工业大学数据结构与算法模拟题5套+答案

13哈尔滨工业大学数据结构试题及答案数据结构试卷（一）；一、单选题（每题2分，共20分）；1.栈和队列的共同特点是()；A.只允许在端点处插入和删除元素；B.都是先进后出；C.都是先进先出；D.没有共同点；2.用链接方式存储的队列，在进行插入运算时().；A.仅修改头指针B.头、尾指针都要修改；C.仅修改尾指针D.头、尾指针可能都要修改；3.以下数据结构中哪一个是非线性结构？()；A.队列B.数据结构试卷（一）一、单选题（每题 2 分，共20分）1. 栈和队列的共同特点是( )。

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

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

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6. 二叉树的第k层的结点数最多为( ).kk-1 A．2-1 B.2K+1 C.2K-1 D. 27. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. 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的元素有（）个，A．1 B．2 C．3 D．410. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

哈尔滨工程大学 哈工大 数据结构与算法基础 笔记 考研真题及答案解析


布丁考研网，在读学长提供高参考价值的复习资料
布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料
布丁考研网，在读学长提供高参考价值的复习资料
布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料
布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料
布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料
布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料

布丁考研网，在读学长提供高参考价值的复习资料
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

A.2 B.3 C.4 D.5 11.能有效缩短关键路径长度的方法是_________。 A． 缩短任意一个活动的持续时间 B． 缩短关键路径上任意一个关键活动的持续时间 C． 缩短多条关键路径上共有的任意一个关键活动的持续时间 D． 缩短所有关键路径上共有的任意一个关键活动的持续时间 12.在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要 探测多个位置， 在查找成功的情况下， 所探测的这些位置的关键字 值________。 A.一定都是同义词 B.一定都不是同义词 C.不一定都是同义词 D.都相同 13.设哈夫曼编码的长度不超过 4，若已对两个字符编码为 1 和 01， 则最多还可以对_______个字符编码。 A．2 B．3 C．4 D．5 14.已知图的邻接表如下所示，根据算法，则从顶点 0 出发深度优先 遍历的结点序列是____________。
k = Partition( A, s, t); while ( k ！= j ) if ( k < j ) k = Partition (A, k+1，t); else k = Partition (A, s，k-1 ); return A[j]; } int Partition (int A[ ], int low ,int high ) { i = low; j = high; pivot = A [ low ]; while ( i < j ) { while ( A[j] >= pivot && i < j ) j --; if (i < j ) A[ i++ ] = A[ j ]; while ( A[j] < pivot && i < j ) i ++; if (i < j ) A[ j-- ] = A[ i ]; } A[ i ] = pivot; return i; }
2．在一个具有 n 个单元的顺序栈中，假定以地址低端（即下标为 0 的 单元） 作为栈底， 以 top 作为栈顶指针， 当出栈时， top 的变化为______。 A. 不变 B. top=0; C.top=top-1; D. top=top+1; 3．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)， 则以 20 为基准记录的一趟快速排序结束后的结果为_________。 A、 10，15，14，18，21，36，40，20 B、 10，15，14，18，20，40，36，21 C、 10，15，14，20，18，40，36，2l D、 15，10，14，18，20，36，40，21 4．任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对 次序________。 A.肯定不发生改变 B.肯定发生改变 C.不能确定 D.有时发生变化 5．用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目 为_________。 A.5 B. 6 C. 8 D. 9 6. 对线性表进行二分查找时，要求线性表必须___________。 A、以顺序方式存储 B、以链接方式存储 C、以顺序方式存储，且数据元素有序 D、以链接方式存储，且数据方式有序 7. 设散列表表长 m=14，散列函数 H(k)=k mod 11。表中已有 15、38、 61、84 四个元素，如果用线性探侧法处理冲突，则元素 49 的存储 地址是_________。 A. 8 B. 3 C. 5 D. 9 8. 若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定 的，则可选择的排序方法是_________。 A.快速排序 B. 堆排序 C.归并排序 D. 插入排序 9. 下面关于 m 阶 B 树的说法正确的是__________。 ① 每个结点至少有两株非空子树 ② 树中每个结点至多有 m-1 个关键字 ③ 所有的叶子都在同一层上 ④ 当插入一个记录引起 B 树分裂后，树增高一层 A. ①②③ B.②③ C. ②③④ D. ①③ 10. 已知一个有序表为（12，18，24，35，47，50，62，83，90，115， 134） ，当折半查找值为 90 的元素时，经过_______次比较后查找 成功。
哈工大 2010 年春季学期 数据结构与算法 A 试 卷 题号 分值 得分 15 一 15 二 20 三 四 20
班号 学号 姓名 总分 70
注 意 行 为 规 范 遵 守 考 场 纪 律
主 管 领 导 签字
一、填空题（每空 1 分，共 15 分） 1. 在顺序存储的二叉树中，编号为 i 和 j 的两个结点处在同一层的条件 是____________。 2． 某二叉树的前序遍历序列是 ABCDEFG， 中序遍历序列是 CBDAFGE， 则其后序遍历序列是_______________。 3．在有 n 个叶子的哈夫曼树中，分支结点总数为___________个。 4．对于含有 n 个顶点 e 条边的连通图，利用 Prim 算法求最小生成树的 时间复杂度为___________。 5. 表达式 a*(b+c)-d 的后缀表达式是___________。 6. 假定一棵二叉树的结点数为 18，则它的最小深度为_______，最大深 度为______。 7. 设有一个 n 阶的下三角矩阵 A， 如果按照行的顺序将下三角矩阵中的 元素（包括对角线上元素）存放在 n(n+1)个连续的存储单元中，则 A[i][j]与 A[0][0]之间有_______ 个数据元素。 8. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这 些初始关键字序列建成的初始堆为________________________。 9. 磁盘文件的归并技术有______________、 ____________、 __________。 10. 设有向图 G 中有向边的集合 E={<1，2>，<2，3>，<1，4>，<4，2>， <4，3>}，则该图的一种拓扑序列为____________________。 11.设一组初始记录关键字序列为(345，253，674，924，627)，则用基 数排序需要进行________趟的分配和回收才能使得初始关键字序列 变成有序序列。 12. 利用 Dijkstra 算法求从有向图顶点 v1 到其他各顶点的最短路径要求 边上权值_________。 二、选择题（每题 1 分，共 15 分） 1．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行 插入和删除运算，则利用___________存储方式最节省时间。 A. 顺序表 B.双链表 C. 单循环链表 D. 带头结点的双循环链表 0
1. 按数组元素有序的一维数组一定是堆。（4 分）
非升序数组一定是最小堆为例说明如下：假设非升序数组为 K1, K2, …,Kn， 则满足 K1 ≤ K2, ≤ … ≤ Kn，则一定满足：Ki ≤ K2i 且 Ki ≤ K2i+1，即满足最小 堆的定义。同理可知，非降序数组一定是最大堆。因此，按数组元素有序的 一维数组一定是堆。 （6 分） 2. 二叉平衡树为 48，40，80，22，45，78 （3 分） 前序：48，40，22，45，80，78 （3 分） 右旋转函数：void R_Rotate(BSTree &p) { lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; } 四、算法 1. 1、本算法不要求将整个记录进行排序，而只进行查找第 j 个记录。 (1)基本思想：改进划分算法，是一次划分将基准元素定位于 k，如果 k==j， 则找到第 j 小的元素；否则，递归地在 k 的左边或右边进行划分，直到 k==j 为止。 (2) 算法详细步骤：略 (3) 算法如下： int Search( int A[ ], int n, int j ) { s = 1; t = n ;
1．对给定的序号 j（1＜j＜n） ，要求在无序记录 A[1]~A[n]中找到按 关键码从小到大排在第 j 位上的记录，试利用快速排序的划分思 想设计算法实现上述查找。 2．设计算法，判断以邻接表存储的有向图中是否存在由顶点 vi 到 顶点 vj 的路径（i≠j） 。
参考答案： 一．填空：1.logi=logj 2.CDBGFEA 3. n-1 4. O(n2) 5.abc+*d6. 5 18 7.i(i+1)/2+j-1 8. 16 18 19 20 30 22 9.多路归并、I/1. 3 12.非负 二、单选：1A2C3A4A5A6C7A8C9B10A11D12C13C14D15B 三、简答：
2. int visited[MAXSIZE]; //指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j) { if(i==j) return 1; //i 就是 j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!visited[k]) return exist_path(k,j);//i 下游的顶点到 j 有路径 }//for return 0; }//else }//exist_path_DFS
A.0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3 15. 在具有 n 个结点的有序单链表中插入一个新结点并仍然有序的 时间复杂度是_________。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 三、简答题：每题 10 分，共 20 分 . 1．一个按数组元素有序的一维数组一定是堆吗？请说明理由。 2. 设有一组初始记录关键字为(45，80，48，40，22，78)，可以构造出 一棵二叉排序树， 若不是平衡树则调整平衡， 并给出其前序遍历该树 的序列，并写出右旋转函数算法。 四、算法设计：每题 10 分，共 20 分 要求： ⑴描述算法设计的基本思想 ⑵描述算法的详细实现步骤 ⑶根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C 或 C++ 或 JAVA 语言实） ，关键之处请给出简要注释。 （栈、队列的存储结构、基本操作可以直接引用）