1. 算法的计算量的大小称为计算的（ ）。
A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）
A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2） 这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法
(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性
4．一个算法应该是（ ）。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5、下面属于逻辑结构的是（ ）
A 顺序表 B哈希表 C 有序表 D 单链表
6、某算法的时间复杂度为O(n2)，表明该算法的（） A 问题规模是n2 B执行时间等于n2 C 执行时间与n2成正比 D问题规模与n2成正比 7、下面关于算法说法错误的是（ ）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
8．从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 9．以下与数据的存储结构无关的术语是（ ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈 10．以下数据结构中，哪一个是线性结构（ ）？
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 11．以下那一个术语与数据的存储结构无关？（ ）
A．栈 B. 哈希表 C. 线索树 D. 双向链表 12．在下面的程序段中，对x的赋值语句的频度为（ ）
FOR i:=1 TO n DO
FOR j:=1 TO n DO x:=x+1;
2n
A． O(2n) B．O(n) C．O(n) D．O(log2) 14．以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈 15. 下列数据中，（ ）是非线性数据结构。
A．栈 B. 队列 C. 完全二叉树 D. 堆 16．连续存储设计时，存储单元的地址（ ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 17．以下属于逻辑结构的是（ ）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表 二、问答：
1. 数据结构是一门研究什么内容的学科？
2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？ 4. 回答问题
（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？
（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。
（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。
5．评价一个好的算法，您是从哪几方面来考虑的？
第二章
1．下述哪一条是顺序存储结构的优点？（ ）
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
2．下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ ）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 6．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。
A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表
7. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
2
A. O(0) B. O(1) C. O(n) D. O(n)
8. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 9．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
A．O（i） B．O（1） C．O（n） D．O（i-1） 16．非空的循环单链表head的尾结点p↑满足（ ）。
A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head 17．循环链表H的尾结点P的特点是（ ）。 A．P^.NEXT:=H B．P^.NEXT:= H^.NEXT C．P:=H D．P:=H^.NEXT
18．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（）
A. p＾.next=h B. p＾.next=NIL C. p＾.next.＾next=h D. p＾.data=-1 19．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。
A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink; C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
20．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、算法设计：
1. 插入算法，在带有头结点的单链表La中第i个元素之前插入e。 2. 删除算法，删除带有头结点的单链表La中第i个元素
3. 将两个有序的带有头结点单链表Ｌａ和Ｌｂ进行合并成一个有序的单链表Ｌｃ算法 4. 将链表Ｌａ进行逆置等操作。
5. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表
中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。 6. (6) 有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆
置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。 7. 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法
去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。
第三章
1. 对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点.
B. 其中一个栈的栈顶到达栈空间的中心点.
C. 两个栈的栈顶在栈空间的某一位置相遇.
D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.
3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A. 不确定 B. n-i+1 C. i D. n-i
4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的
5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。
A. i B. n-i C. n-i+1 D. 不确定
6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）【中山大学 1999 一、8(1分)】
A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop
14. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。
A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1 C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1
15. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 16. 栈在（ ）中应用。【中山大学 1998 二、3（2分）】
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 17. 一个递归算法必须包括（ ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分
19. 表达式a*(b+c)-d的后缀表达式是( )。
A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd
21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构 B. 队列C. 线性表的链式存储结构 D. 栈 22. 用链接方式存储的队列，在进行删除运算时（ ）。【
A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。
A．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改
24. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。
A．队列 B．多维数组 C．栈 D. 线性表 25. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 26. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。
A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 27. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
28. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1 31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front 32. 栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 34. 栈和队都是（ ）
A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构
35. 设栈S和队列Q的初始状态为空，元素a1，a2，a3，a4,a5和a6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是a2，a4，a3,a6,a5,a1则栈S的容量至少应该是( )。
A． 6 B. 4 C. 3 D. 2 36. 用单链表表示的链式队列的队头在链表的（ ）位置。
A．链头 B．链尾 C．链中
第四章 串
1．下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 ．串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数 3．空格串是指__(1)__，其长度等于___(2)__。 4．组成串的数据元素只能是________。
5．一个字符串中________称为该串的子串 。
第 5 章 数组和广义表
1、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。
A. BA+141 B. BA+180 C. BA+222 D. BA+225
2. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。
A. 808 B. 818 C. 1010 D. 1020
3. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
A. 1175 B. 1180 C. 1205 D. 1210
4、二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。
A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9] 5、. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i A. 55 B. 45 C. 36 D. 16 1. 数组的存储结构采用_______存储方式。 2. 设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为__（1）_；如按列优先顺序存储,则元素A[-18,-25]的存储地址为__（2）_。 3. 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）_。 4. 将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。 5. 二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储) 6. 设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为_______。 第六章 树和二叉树 1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A．5 B．6 C．7 D．8 3. 在下述结论中，正确的是（ ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 4. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A．9 B．11 C．15 D．不确定 9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个 A．4 B．5 C．6 D．7 10．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。 A．M1 B．M1+M2 C．M3 D．M2+M3 11．具有10个叶结点的二叉树中有（ ）个度为2的结点， A．8 B．9 C．10 D．ll 12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A． 250 B． 500 C．254 D．505 E．以上答案都不对 13. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 16. 有关二叉树下列说法正确的是（ ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 17．二叉树的第I层上最多含有结点数为（ ） I I-1I-1I A．2 B． 2-1 C． 2 D．2 -1 18. 一个具有1025个结点的二叉树的高h为（ ） A．11 B．10 C．11至1025之间 D．10至1024之间 19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点 A．2h B．2h-1 C．2h+1 D．h+1 20、对于有n 个结点的二叉树, 其高度为（ ） A．nlog2n B．log2n C．log2n|+1 D．不确定 21对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 22．树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 23．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 24. 线索二叉树是一种（ ）结构。 A． 逻辑 B． 逻辑和存储 C． 物理 D．线性 25．n个结点的线索二叉树上含有的线索数为（ ） A．2n B．n－l C．n＋l D．n 26．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ） 【南开大学 2000 一、2】 A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树 27．下述编码中哪一个不是前缀码（ ）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 28．下面几个符号串编码集合中，不是前缀编码的是（ ）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} 二、应用题 1、将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） D G A J H I E B C L M K N O F P 2、已知二叉树的先序序列: CBHEGAF, 中序序列: HBGEACF, 试构造该二叉树 3、已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK 4、、定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。 三、算法设计题： 1. 二叉树的创建 2. 求叶子个数 3. 求总的结点个数 4. 求树的深度 5. 对树进行层次遍历 6. 进行查询特定元素等算法。 第七章 1．图中有关路径的定义是（ ）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。 2 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 3．一个n个顶点的连通无向图，其边的个数至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ ）条边。 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（ ）。【 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 A．1/2 B．2 C．1 D．4 8．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A．逆拓扑有序 B．拓扑有序 C．无序的 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确 9无向图G=(V,E),其中： V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 10. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 23 A. O(n) B. O(n+e) C. O(n) D. O(n) 【合肥工业大学 2001 一、2 （2分）】 11．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={ A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 12．一个有向无环图的拓扑排序序列（ ）是唯一的。 A．一定 B．不一定 13. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 A．G中有弧 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 15. 下面关于求关键路径的说法不正确的是（ ）。 A．求关键路径是以拓扑排序为基础的 B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D．关键活动一定位于关键路径上 16．下列关于AOE网的叙述中，不正确的是（ ）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 二、基础知识题 1．有向图的邻接表存储如下：（1）．画出其邻接矩阵存储；（2）．写出图的所有强连通分量；（3）．写出顶点a到顶点i的全部简单路径。 2．已知无向图如下所示： （1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。【燕山大学 2000 五 （5分）】 234v1 51v2 51v3 v416 v523 v64 第2题图 第3题图 3．已知某图的邻接表为 （1）．写出此邻接表对应的邻接矩阵；（2分） （2）．写出由v1开始的深度优先遍历的序列；（2分） （3）．写出由v1开始的深度优先的生成树；（2分） （4）．写出由v1开始的广度优先遍历的序列；（2分） （5）．写出由v1开始的广度优先的生成树；（2分） 4、一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。 5、下图是带权的有向图G的邻接表表示法，求： （1）．以结点V1出发深度遍历图G所得的结点序列； （2）．以结点V1出发广度遍历图G所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。 第九章 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定N为线性表中结点数，且每次查找都是成功的。 2 A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N 4. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 5. 具有12个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5 6. 折半查找的时间复杂性为（ ） 2nn A. O（n） B. O（n） C. O（nlog） D. O（log） 7．当采用分快查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 8．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 【合肥工业大学2000一、4（2分）】 A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 9. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。【合肥工业大学 2001 一、4 （2分）】 A. LL B. LR C. RL D. RR 10. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链 地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。 A．1 B. 2 C. 3 D. 4 11 下面关于哈希(Hash，杂凑)查找的说法正确的是( ) A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的 C．不存在特别好与坏的哈希函数，要视情况而定 D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 12. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）) 个链 表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）) （1） A．17 B. 13 C. 16 D. 任意 13设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 【南京理工大学 2001 一、15 （1.5分）】 A．8 B．3 C．5 D．9 14 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将 关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （1）元素59存放在散列表中的地址是（ ）。 A． 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次数是（ ）。 A． 2 B. 3 C. 4 D. 5 基础知识题： 1、设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=key MOD 13， 即关键字对13取模，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。 2、采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51 （1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。 3、设散列函数为H（K）=K MOD 13，给定的键值序列为13,41,15,44,06,68,12,25,38,64,19,49，画出用链地址法处理冲突构造得的哈希表 4、用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度. 5、已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤：【北方交通大学 1996 四】 （1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL（7分） （2）构造一棵二叉排序树，如果对每个关键字的查找概率相同，求查找成功时的平均查找长度ASL。 第十章 1. 下列四个序列中，哪一个是堆（ ） A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 2. 下列排序算法中，第一趟排序完毕后，其最大或最小元素一定在其最终位置的算法是 （ ） A．归并排序 B．直接插入排序 C．快速排序 D．冒泡排序 3. 下面给出的4种排序方法中，排序过程中的比较次数与初始排序次序无关的是（ ）。 A．选择排序法 B．插入排序法 C．快速排序法 D．堆排序法 4. （）从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。 A．二叉排序树 B. 大顶堆 C．小顶堆 D. 平衡二叉树 5. 对于序列(49,38,65,97,76,13,27,50)按由小到大进行排序，（ ）是初始步长d=4的 希尔排序法第一趟的结果。 A. 49,76,65,13,27,50,97,38 B. 13,27,38,49,50,65,76,97 C. 97,76,65,50,49,38,27,13 D. 49,13,27,50,76,38,65,97 6. 若一组纪录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始 堆为（ ） A．79，46，56，38，40，84 B．84，79，56，38，40，46 C．40，38，46，56，79，84 D．40，38，46，84，56，79 7. 若对序列（tang,deng,an,wang,shi,bai,fang,liu）采用选择排序法按字典顺序进行排 序，下面给出的四个序列中，（ ）是第三趟的结果 A. an,bai,deng,wang,tang,fang,shi,liu B. an,bai,deng,wang,shi,tang,fang,liu C. an,bai,deng,wang,shi,fang,tang,liu D. an,bai,deng,wang,shi,liu,tang,fang 8. 下列序列中，满足堆定义的是（ ） A.（100，86，48，73，35，39，42，57，66，21） B.（12，70，33，65，24，56，48，92，86，33） C.（103，97，56，38，66，23，42，12，30，52，6，26） D.（5，56，20，23，40，38，29，61，36，76，28，100） 17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( )的两趟排序后的结果。 A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 18．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。 A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 19．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。 A. 选择 B. 冒泡 C. 快速 D. 插入 20．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡 21．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（ ）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡 22．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序 23．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 24．下列序列中，（ ）是执行第一趟快速排序后所得的序列。 A. [68，11，18，69] [23，93，73] B. [68，11，69，23] [18，93，73] C. [93，73] [68，11，69，23，18] D. [68，11，69，23，18] [93，73] 25．有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。 A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20 26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。 A．(38,40,46,56,79,84) B. (40,38,46,79,56,84) C．(40,38,46,56,79,84) D. (40,38,46,84,56,79) 基础知识题： 1、判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。 （1）100，85，98，77，80，60，82，40，20，10，66 （2）100，98，85，82，80，77，66，60，40，20，10 （3）100，85，40，77，80，60，66，98，82，10，20 （4）10，20，40，60，66，77，80， ，85，98，100 82 因篇幅问题不能全部显示，请点此查看更多更全内容