数据结构练习题

1.设带头结点的单链表Head为空的判断条件是( )

2.用数组a[1..n]表示循环队列Sq, 则当循环队列Sq是满时，队列有（ ）元素。 3．设有150个记录要存储到散列表中, 要求利用线性探测再哈希法解决冲突, 同时要求找到所需记录的平均比较次数不超过2次,则散列表的长度至少需要设计为（ ） 4若m叉树中A有3个兄弟，结点B是A的双亲，则节点B的度是（ ）。

5 有一个10×10的下三角矩阵a ,若采用按行优先进行顺序存储在一个一维数组Sa[N]中,则N的值是( )。

6.若在一个表有625个元素，且查找每个元素的概率相同，那么在采用分块查找时，每块的长度为（ ），平均查找长度最小，此时的平均查找长度是( )

7.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、（ ） 和 （ ） 。

8.求顺序表和单链表的长度算法，其时间复杂度分别是（ ）和（ ）。

9.线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的（ ） 也是相邻的。 10.空格串的长度为串中所包含 （ ） 字符的个数，空串的长度为 （ ） 11.加上表示指向前驱和 （ ） 的线索的二叉数称为线索二叉树。 二、选择题

1.一棵具有n个叶子结点哈夫曼树，共有( )个结点。 A 2n B2n-1 C2n+1 D2n-1

2.下面（ ）的时间复杂性最好即执行时间最短 A、O(n) B、O(logn)

C、O(nlogn) D、O(n2)

3.相对于顺序存储而言，链式存储的优点是（ ） A随机存取 B节约空间 C增、删操作方便 D节点间关系简单

4.设单链表中指针p指向结点ai ,若要删除ai之后的结点(若存在),需要修改指针的操作为( )

A p->next=p->next->next B p=p->next C p=p->next->next D p->next=p->data 5.允许对队列进行的操作有( )。

A、删除队首元素 B、取出最近进队的元素 C、在最早入队元素之前插入元素 D、排序

6.若让元素d,a,c,b依次进栈,则出栈次序不可能出现以下哪种情况( )。 A d,c,b,a B a,c,d,b C a,b,c,d D c,b,d,a

7.在具有n（n＞l）个结点的完全二叉树中，结点i（2i＞n）的左孩子结点是( ) A 2i B 2i+1 C 不存在 D 是2i-1

8.深度为5的满二叉树共有（ ）个分支结点 A、32 B、15 C 30 D、31

9.任何一个有向图的拓扑序列（ ）

A可能不存在。 B 只有一个。 C 一定有多个。 D 有一个或者多个。

10.已知二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列是（ ）

A CBEFDA B FEDCBA C CBEDFA D 不定

11.一个三元组表用于表示一个（ ）

A 线性表 B 广义表 C双向链表 D 稀疏矩阵。

12.设广义表L=（a,(((f,g),e),(c,d))）则表达式GetTail(GetHead(GetTail(L)))的值为( ) A（d） B (e) C g D e

13.利用4,5,6,7,8作为叶子结点的权值,生成一棵赫夫曼树,该树的带权路径长度为( ) A、67 B、68 C、69 D、70

14.若无向图G=中含有7个顶点，要保证图在任何情况下都是连通的，则需要的边数最少是（ ）条。

A. 6 B 15 C 16 D 21

15.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为 82的结点时，( )次比较后查找成功。 A 1 B 2 C 4 D 8

1.从一个长度为100的顺序表中删除第30个元素时需向前移动 个元素 A、70 B、71 C、69 D、30

2.在一个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为______。 A、 top不变 B、top=0 C、top=top-1 D、top=top+1

3.已知广义表：A=(a, b), B=(A,A),C=(a, (b,A),B),则tail(head(tail(C)))=()。 A、(a) B、A C、(b) D、(A)

4.在一个单链表中,若要删除p指针所指结点的后继结点,则执行 A、p-> next; p-> next=p-> next-> next; B、p-> next=p-> next-> next; C、p=p-> next;

D、p=p-> next->>next;

5.在一个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行___。

A、front-> next=s； front=s； B、s-> next=rear; rear=s； C、rear-> next=s; rear=s； D、s-> next=front; front=s；

6.在一棵度为3的树中度为3的结点数为3个,度为2的结点数为1个,度为1的结点数为1个,那么度为0的结点数为____个 A、6 B、7 C、 8 D、9

7. 在一棵完全二叉树中,若编号为i的结点有右孩子,则该结点的右孩子编号为___。 A、2i B、2i+1 C、2i-1 D、i/2

8.在一个有向图中,所有顶点的入度之和等于所有弧数和___倍。 A、1 B、2 C、3 D、4

9.n个结点的线索二叉树上含有的线索数为（ ）。 A、 2n B、n-1 C、n+1 D、 n

10．若已知一棵二叉树先序序列为debac，后序序列为dabec，则其前序序列为( ) 。 A. acbed B. decab C. deabc D. cedba

11．下列存储形式中，( ) 不是树的存储形式。

A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法

12．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 13．采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。 A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构 D.随机表 链式存储结构

14．就平均查找速度而言，下列几种查找速度从慢至快的关系是（ ） A.顺序 折半 哈希 分块 B.顺序 分块 折半哈希 C.分块 折半 哈希 顺序 D.顺序 哈希 分块 折半 三、解答题

1 已经带权无向图如图1所示，利用克鲁斯科尔(Kruskal)算法，画出该无向图的最小生成树的每一步。

图1 带权无向图

2 如图2所示的有向图,请分别给出该图的邻接矩阵表示,逆邻接表表示。

图 2 有向图

3对于待排序序列{52 49 80 36 14 58 61}

以快速排序算法来将该序列进行排序，写出各趟排序后的结果。

4有序表按关键码排列如下：{7，14，18，21，23，29，31，35，38，42，46，49，52} [1]写出在表中用折半查找关键码为14的数据元素的过程，

[2]并且画出有序表折半查找的判断树,并且求出等概率查找成功的平均查找长度ASL。 5如图3所示AOE是某个工程的计划图,各个顶点表示事件,边表示活动,边上的权值表示各活动所需要的时间

[1]计算事件v4最早发生时间和最晚发生时间. [2]求该AOE图的关键路径.

图3 AOE图

设关键字的输入序列为{ 5, 4, 2, 8, 6, 9 }

6．（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。

7．（4分）上面的数据作为待排序的数据，写出用快速排序进行一趟划分后的数据序列 8. 已知序列{ 40, 55, 49, 73, 12, 27, 98, 81, , 36 }请给出堆排序每一趟的结果。

9.设有一组关键字关键码集为 {47，7，29，11，16，92，22，8，3}，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL。 10.用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。 四、应用题

1.欲传输一段电文如下：CATEATDATACAECATAEAAE。设计出这段电文中的每个字符的哈夫曼编码，并计算整段电文的编码长度。

2. 已知序列{ 40, 55, 49, 73, 12, 27, 98, 81, , 36 }请给出堆排序每一趟的结果。

3.设有一组关键字关键码集为 {47，7，29，11，16，92，22，8，3}，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL。 4. 二叉树的先序遍历序列为 A B C D E F G H I，中序遍历序列为 B C A E D G H F I，画出这棵二叉树。

5给定叶子结点的权值集合{15，3，14，2，6，9，16，17}，构造相应的哈夫曼树，并计算它的带权路径长度。

6.画出该图的邻接矩阵和邻接表

7如图所示AOE是某个工程的计划图,各个顶点表示事件,边表示活动,边上的权值表示各活动所需要的时间

[1]分别计算事件v4的最早发生时间和最晚发生时间. [2]求该AOE图的关键路径.

8．画出树的孩子兄弟表示法示意的树或森林。

9.写出下图的每个顶点的入度与出度。

五、算法题

下面是一个使用栈stack实现对二叉树进行非递归先根遍历的函数,请在标号处填写合适的语句。 程序:

1. Void preorder(bitree *T) {bitree *stack[m]; int top;

if(T!=NULL) {top=1;

stack[top]=(1);

while( (2) )

{p=stack[top]; top--;

printf(“%d”,p->data);

if(p->rchild!=NULL){ (3) ; stack[top]=p->rchild;} if( (4) ) { top++; (5) ;}

} } }

2.写出程序段的功能,并给出一个测试用例（一个输入数据和一个输出结果）。 void conversion() {

Stack s; int n;

SElemType e; initstack(s);

printf(\"Please input number:\"); scanf(“%d”,&n); while(n)

{push(s,n%8); n=n/8; }

while(!stackempty(s)) {pop(s,e);

printf(“%d”,e); }

}