当前位置：文档之家 › 哈工大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

哈尔滨工程大学数据结构历年试卷试卷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(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套+答案

哈尔滨工业大学数据结构与算法模拟题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个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

布丁考研网，在读学长提供高参考价值的复习资料
哈工大国家级课《数据结构与算法》

哈工大国家级课《数据结构与算法》

29. 假设用于通信的电文由字符集{a，b，c，d，e，f，g，h}中的字母构成，这 8 个字母在 电文中出现的概率分别为{0.07 ，0.19 ，0.02 ，0.06 ，0.32，0.03，0.21 ，0.10}。 (1)为这 8 个字母设计哈夫曼编码。 (2)若用三位二进制数(0-7)对这个 8 个字母进行等长编码，则哈夫曼编码的平均码长是
若有右子树，则 i 应满足的条件是( )。
A．2i+1 <= n
B．2i <= n
C．n/2<= i
D．2i-l <= n
12. 在一棵高度为 k 的二叉树中，最少含有( )个结点。
A．2k-1
B．2k-l
C．2k-1
D．k
13. 在一棵高度为 k 的二叉树中，最多含有( )个结点。
A．2k-1
B．2k-l
(2)编号为 i 的结点的双亲结点(若存在)的编号是多少?
(3)编号为 i 的结点的左孩子结点(若存在)的编号是多少？
(5)编号为 i 的结点有右兄弟的条件是什么，其右兄弟的编号是多少？ (6)编号为 i 的结点有右兄弟的条件是什么，其右兄弟的编号是多少？ 25. 设二叉树包含的结点数为 1，3，7，2，12。 (1)画出两棵高度最大的二叉树。 (2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。 26. 试找出分别满足下面条件的所有二叉树： (1)前序序列和中序序列相同； (2)中序序列和后序序列相同； (3)前序序列和后序序列相同； (4)前序、中序和后序序列相同。 27. 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列 和中序序列均能惟一地确定一棵二叉树，但由前序序列和后序序列却不一定能惟一地确 定一棵二叉树。 (1)己知一棵二叉树的前序序列和中序序列分别为 ABDGHCEFI 和 GDHBAECIF，请画出此 二叉树。 (2)已知一棵二叉树的中序序列和后序序列分别为 BDCEAFHG 和 DECBHGFA。请画出该二 叉树。 (3)已知两棵二叉树的前序序列和后序序列均为 AB 和 BA，请画出这两棵不同的二叉树。 28. 对下图所示二元树： (1)写出该二叉树的前序、中序和后序序列； (2)画出中该二叉树的顺序存储结构、左右链存储结构和带头结点的中序线索存储结构。

哈工大2010秋-《C++与数据结构》A(B5)

分别为 5, 25, 3, 6, 10, 11, 36, 4 ，请完成下列问题：
a) b)
为这 8 个字母设计 Huffman 编码，并画出其相应的 Huffman 树； 设 Huffman 树中每个结点有三个域： lChild 、 rChild 和 element ，试设计一个递归算法 【要求】 ：如果采用非递归算法，将视为无效；必须用 求该 Huffman 树的带权路径长度。 C++语言给出该递归算法对应的函数说明及实现。
第 4 页 （共 10 页）
试 题： 《高级语言程序设计与数据结构》 （A 卷） 班号：
姓名：
4． （11 分）请分别回答下列问题： a) b)
请简述 C++语言中 const 关键字、类型适应的常见用法及注意事项； （6 分） 以 C++为例，请简述你对面向对象的程序设计中多态性的理解。 （5 分）
M 1 M K 个元素是
。
5． 最大容量为 N 的循环队列，队尾指针是 rear ，队首指针为 front ，则队满的条件
是 。 。
6． 已知模式串 S ' ababaabab ' ，则其 next 数组值为
7． 设有数组 A i, j ， 数组的每个元素长度为 3 字节，i 的值为 1 到 8， j 的值为 1 到 10，
p , p , p , , p ，则由序列 1, 2, 3, , n 可通过一个栈得到序列 p1 , p2 , p3 , , pn 。
1 2 3 n
第 2 页 （共 10 页）
试 题： 《高级语言程序设计与数据结构》 （A 卷） 班号：
姓名：
2． （20 分）已知某带权无向图的邻接矩阵三元组压缩存储如下图（本三元组压缩存储中，对于

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

2022年哈尔滨师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

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

A.60B.66C.18000D.333、连续存储设计时，存储单元的地址（）。

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、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

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

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

数据结构与算法(Python版)《数据结构》参考答案(A卷)

数据结构与算法(Python版)《数据结构》参考答案(A卷)引言：数据结构与算法是计算机科学中的重要基础知识，对于程序员来说至关重要。

本文将以Python版数据结构与算法的《数据结构》参考答案(A卷)为主题，通过引言概述和四个部份的详细阐述，为读者提供准确的内容。

一、线性结构1.1 数组- 数组是一种线性结构，它由一系列相同类型的元素组成。

- 数组的特点是可以通过索引快速访问元素，时间复杂度为O(1)。

- Python中的列表(list)可以看做是一种动态数组，可以根据需要动态调整大小。

1.2 链表- 链表也是一种线性结构，它由一系列节点组成，每一个节点包含一个数据元素和一个指向下一个节点的指针。

- 链表的特点是可以快速插入和删除元素，时间复杂度为O(1)。

- Python中没有内置的链表数据结构，但可以通过自定义类来实现链表的功能。

1.3 栈- 栈是一种特殊的线性结构，它只允许在一端进行插入和删除操作，这一端被称为栈顶。

- 栈的特点是后进先出(LIFO)，即最后插入的元素最先被删除。

- Python中可以使用列表作为栈的实现，利用append()和pop()方法进行操作。

二、非线性结构2.1 树- 树是一种非线性结构，它由一组节点和一组连接节点的边组成。

- 树的特点是每一个节点可以有零个或者多个子节点，节点之间存在层次关系。

- Python中可以使用类来定义树的节点，通过引用来连接节点。

2.2 图- 图也是一种非线性结构，它由一组顶点和一组边组成。

- 图的特点是顶点之间可以有多个边相连，边可以有方向。

- Python中可以使用邻接矩阵或者邻接表来表示图，通过列表或者字典来存储图的数据。

2.3 堆- 堆是一种特殊的树形数据结构，它满足堆属性，即父节点的值总是大于或者小于它的子节点。

- 堆的特点是可以快速找到最大或者最小值的元素。

- Python中可以使用heapq模块来实现堆的功能。

三、排序算法3.1 冒泡排序- 冒泡排序是一种简单的排序算法，它重复地比较相邻的元素，并交换顺序不符合要求的元素。

2010年黑龙江省数据结构试题及答案修改二必过技巧

A.整形 B.引用型
C.指针型 D.常值引用型?
26、在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（ ）型调整以使其平衡
A LL B LR C RL D RR
C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s
D．s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s
12、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A 插入排序和快速排序 B 归并排序和快速排序
C 选择排序和归并排序 D 插入排序和归并排序
42、从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A.O(1) B.O(n)
C.O(1Ogzn) D.O(n2)
A 5,4,3,2,1 B 4,5,3,2,1 C 4,3,5,1,2 D 1,2,3,4,5
8、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A． HL＝ps p一>next＝HL
B． p一>next＝HL；HL＝p3
B．二维数组是其数据元素为线性表的线性表
C．栈的操作方式是先进先出
D．队列的操作方式是先进后出
37、由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。
A．24 B．48
C． 72 D． 53

历年年哈工大计算机考研试题(无水印)

硕士研究生入学考试初试专业课资料
计算机专业基础
计算机考研历年真题(1991年-2008年) 友情分享！余人玫瑰手留余香！
第 3 页共 3 页
第共
第 3 页共 3 页
七、依次读入数据元素序列{a，b，c，d，e，f，g}j进栈每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行则栈空时弹出的元素构成的序列是以下那些序列？（
{d ，e，c，f，b，g，a}， {f，e，g，d，a，c，b}
（低电平有效）作访作读
作读写命令信号（高电平为读，低电平为写）。

有一系统程序编译后为
根数据线，允许输出，允许写，片选
允许写，
允许输出，片选
允许输出，片选，允许写。

数据结构--2010河北工大考研题及答案

2010年一、1. 所谓的双向链表，是指在每一个结点中，有两个指针域，其中一个指向该结点的直接后继结点，而另一个则指向。

【答案】其直接前趋结点2. 线性表的顺序存储结构是一种存取的存储结构。

【答案】随机3. 若一棵根树的每个结点最多只有孩子，且孩子又有之分，次序不能颠倒，则称此根树为。

【答案】两个，左、右，二叉树4. 满二叉树是指高度为k，且有个结点的二叉树。

二叉树的每一层上，最多有个结点。

【答案】2k-1 2i-15. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。

【答案】哈希表查找法6. 广义表(a,(a,b),d,e,((i,j),k))的长度是，深度是。

【答案】5，3二、1.下面哪一种情况不利于发挥堆排序的优势。

【答案】待排序的数据量小2.如果采用直接选择排序法来排序一个长度为5，且已按相反顺序排序的数组，共需的比较次数是。

【答案】103. 在一棵包含n个结点的顺序二叉树上,最远的两个结点有多远。

【答案】在一棵树包含N个节点完全二叉树上,相距最远的两节点的距离是2logN-34. 折半查找不成功时，指针Low和High的关系是。

【答案】Low>High5.在待排元素序列基本有序的前提下，下面给出的几种排序方法效率最高的是。

【答案】直接插入排序6.设A是一个包含有10个数据元素的有序数组，如果我们利用折半查找法在A中查找任意的数据元素X，假定在确定目标元素是否等于、小于或大于A[i]时仅需比较一次。

则平均的查找成功时间是。

【答案】2.9三、1.能在线性表上进行的操作，就一定能在栈上进行。

【答案】错2. 如果关键字是主关键字的话，则对一个无序的数据元素序列经按主关键字排序后得到的结果是唯一的。

【答案】对3.由于线性链表的存取必须顺序进行，所以在线性链表上删除一个结点时，必须移动其后的所有结点，才能继续保持一个顺序存取的关系。

【答案】错4. 线性表顺序存储结构的存储密度大于线性表的链式存储结构。

  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 语言实） ，关键之处请给出简要注释。 （栈、队列的存储结构、基本操作可以直接引用）