数据结构习题集

while(pa)

{pc=hc; qc=hc->next; search= ; while(qc&&search) {if(pa->data<=qc->data) ; else { pc=qc; qc= ; } }

fa= ; pa= ; fa->next= ; ; } }

六、设下图二叉树B2的存储结构为二叉链表,root为根指针,结点结构为:(1child,data,rchild)其中:lchild,rchild分别为指向左右孩子的指针,data为字符型。(共10分)

1. 对下列二叉树B2,执行下列算法traversel(root),试指出其输出结果;

2.假定二叉树B2共有n个结点,试分析算法traversal的时间复杂度。结点类型定义如下:

struct node { chardata;

struct node *lchild,*rchild;

}; 算法如下:

void traversal(struct node *root) { if(root)

{ prinft(“%c”,root->data); traversal(root->lchild); prinft(”%c”,root->data); traversal(root->rchild); } }

七、算法设计题(要求:(1)写出所用数据结构的类型定义和变量说明;(2)写出算法,并在相关位置加注释,以提高算法的可读性。)

36

二叉树B2

1.试设计一算法:输入一个有m行n列的整数矩阵,然后将每一行的元素按非减次序输出。例如,若输入:

4,3,5,6,2 9,8,1,2,8 7,1,2,3,8 则输出如下结果: 2,3,4,5,6 1,2,8,8,9 1,2,3,7,8

2.如果字符串的一个子串(其长度大于1)的各个字符均相同,则称之为等值子串。试设计一算法:输入字符串S,以’!’为结束标志,如果串S中不存在等值子串,则输出信息:”无等值子串”,否则求出(输出)一个长度最大的等值子串。 例如,若S=”abcl23abcl23!”,则输出:”无等值子串”;

又如,若S=”abcaabcccdddddaaadd!”,则输出等值子串:”ddddd”。(共20分)

北京理工大学2001年程序设计(含数据结构)试题

第二部分 数据结构(共50分)

一、选择题(12分,每题2分)

1.下列数据中哪些是非线性数据结构 。

A.栈 B.队列 C.完全二叉树 D.堆 2.静态链表中指针表示的是 。 A.内存地址 B.数组下标 C.下一元素地址 D.左、右孩子地址

3.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时 。 A.仅修改队头指针 B.仅修改队尾指针 C.队头,队尾指针都要修改 D.队头,队尾指针都可能要修改

4.在下列排序算法中,哪一个算法的时间复杂度与初始排列无关 。 A.直接插入排序 B.起泡排序 C.快速排序 D.直接选择排序

5.二叉树第i层结点的结点个数最多是(设根的层数为1) 。 A.2i-1 B.2i-1 C.2i D.2i-1 6.树的后根遍历序列等同于该树对应的二叉树的 。 A.先序序列 B.中序序列 C.后序序列 二、填空(8分,每空1分)

37

1.数据结构中评价算法的两个重要指标是——。

2.顺序存储结构是通过 表示元素之间的关系的。链式存储结构是通过 表示元素之间的关系的。

3.AOV网中,结点表示 ,边表示 。AOE网中,结点表示 ,边表示 。 4.哈夫曼树是 。

三、求解下列问题(25分,每题5分) 1.请用C语言给出线性链表的类型定义。

2.已知二叉树的先序序列:CBHEGAF,中序序列:HBGEACF,试构造该二叉树。 3.设散列表的地址空间为0到12的存储单元,散列函数为:h(key)=key mod 13,用链地址法解决冲突,初始时散列表为空。现依次将关键字25,33,48,25,43,38,39插入散列表,试画出完成上述所有插入操作后散列表的状态,并计算在等概率的情况下,在该表中查找成功的平均查找长度。 4.给出如下图所示的图形。 1)试写出该图的邻接表;

2)试写出该图从结点0出发的深度优先遍历序列和广度优先遍历序列,并画出遍历过程中所经的路径。

5.全国统考答题

对上图,按迪杰斯特拉算法求出从结点0到其余各点的最短路径,并给出在求解过程中数组distance的变化状态。

6.单独考试答题(可在5或6中任选一题做)

给出关键字序列27,18,21,77,26,45,66,34试写出快速排序的过程。 四、算法题(12分)(请在算法的主要步骤上加注释)

1.下面是用C语言编写的对不带头结点的单链表进行就地置逆的算法,该算法用L返回置逆后链表的头指针。试在空缺处填入适当的语句。 void reverse(1inklist&L) { p=NULL;q=L; while(q!=NULL)

{

q->next=p; p=q;

38

} }

2.全国统考答题

设二叉树用二叉链表存储,试编写按层输出二叉树结点的算法。 3.单独考试答题(可在2或3中任选一题做)

试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法。 void delete(Linklist &L)

北京邮电大学2001年数据结构试题

一、选择题(10分,每题2分) 1.B+树是应用在( )文件系统中。 ①ISAM ②VSAM

2.将一棵树t转换为孩子-兄弟链表表示的二叉树h,则t的后根遍历是h的( )。 ①前序遍历 ②中序遍历 ③后序遍历

3.一个有向无环图的拓扑排序序列( )是惟一的。 ①一定 ②不一定

4.将10个元素散列到100000个单元的哈希表中,则( )产生冲突。 ①一定会 ②一定不会 ③仍可能会

5.若要求尽可能快地对序列进行稳定的排序,则应选( )。 ①快速排序 ②归并排序 ③冒泡排序 二、填空题(20分,每空2分) 1.数据的逻辑结构是指 。

2.区分循环队列的满与空,只有两类办法,它们是 和 。

3.用一维数组B以列优先存放带状矩阵A中的非零元素A[i,j](1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A中第 行、第 列的元素。 4.字符串’ababaaab’的nextval函数值为——。

5.下图中的强连通分量的个数为 个。

6.外部排序的基本方法是归并排序,但在之前必须先生成 。

7.若不考虑基数排序,则在排序过程中,主要进行的两种基本操作是关键字的 和记录的

三、简答题(15分,每题5分)

1.特殊矩阵和稀疏矩阵哪种压缩存储后会失去随机存取的功能?为什么?

39

2.试问线索二叉树的目的何在?

3.在多关键字排序时,LSD和MSD两种方法的特点是什么? 四、应用题(25分,每题5分)

1.画出按下表中元素的顺序构造的平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

{15,12,24,3,27,21,18,6,36,33,30,26,3}

2.假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成,它们在电文中出现的频率分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}。 (1)为这7个字母设计哈夫曼编码;

(2)对这7个字母进行等长编码,至少需要几位二进制数?哈夫曼编码比等长编码使电文总长压缩多少?

3.试推导当总盘数为n时的Hanoi塔的移动次数。

4.一棵满k叉树,按层次遍历存储在一维数组中,试计算结点下标为u的结点的第i个孩子的下标以及结点下标为v的结点的父母结点的下标。

5.有一图的邻接矩阵如下,试给出用弗洛伊德算法求各点间最短距离的矩阵序列A(1)、A(2)、A(3)和A(4)。

A= 0 2 ∞ ∞ ∞ 0 1 6 5 ∞ 0 4 3 ∞ ∞ 0 五、算法(30分,每题10分)

1.在单链表中,每个结点含有5个正整型的数据元素(若最后一个结点的数据元素不满5个,以值0填充),试编写一算法查找值为n(n>0)的数据元素所在的结点指针以及在该结点中的序号,若链表中不存在该数据元素则返回空指针。

2.将一组数据元素按哈希函数H(key)散列到哈希表m(0..m)中,用线性探测法处理冲突(H(key)+1、H(key)+2、?、H(key)-1,假设空单元用EMPTY表示,删除操作是将哈希表中结点标志位从INUSE标记为DELETED,试写出该散列表的查找、插入和删除三个基本操作算法。

3.给出算法将二叉链表表示的表达式二叉树按中缀表达式输出,并加上相应的括号。

北京航空航天大学2001年 数据结构与程序设计试题

一、问答题(本题10分)

一般情况下,线性表可以采用哪几种存储结构?请分别叙述每一种存储结构的构造原理与特点。

二、(本题10分)

已知AOE网为G=(V,E),V={v1,v2,v3,v4,v5,v6,v7,v8,V9,vl0},E={a1,a2,a3,a4,a5,a6,a7,a8,a9,al0,a11,a12,a13,a14},其中:

40

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4