9512.net
甜梦文库
当前位置:首页 >> >>

测试一下自己的水平


济南铁道职业技术学院

专升本辅导教材

数据结构

测试一下自己的水平

一、判断题 (每小题 1 分,共 15 分) 1.非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( ) 2.数组是一种没有插入与删除操作的线性结构。( ) 3.稀疏矩阵中值为 0 的元素分布有规律,因此可以采用三元组方法进行压缩存储。( ) 4.空串与由空格组成的串没有区别。( ) 5.将 T 在 S 中首次出现的位置作为 T 在 S 中的位置的操作称为串的模式匹配。( ) 6.深度为 h 的非空二叉树的第 i 层最多有 2h-1 个结点。( ) 7.完全二叉树就是满二叉树。( ) 8.已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。( ) 9.非空二叉排序树的任意一棵子树也是二叉排序树。( ) 10.有向图是一种非线性结构。( ) 11.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( ) 12.AOE 网是一种带权的无环连通图。( ) 13.折半查找方法适用于按值有序的线性链表的查找。( ) 14.哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。( ) 15.选择排序过程中元素之间的比较次数与原始序列的状态无关。( ) 二、单项选择题 (每小题 2 分,共 20 分) 1.若长度为 n 的线性表采用顺序存储结构,删除它的第 i 数据元素之前,需要先依次向前移动_______个 数据元素。( ) A.n-i B.n+i C.n-i-1 D.n-i+1 2.在单链表中,已知 q 指的结点是 q 指的结点的直接前驱结点,若在 q 和 p 指的结点之间插入一个由 s 指的结点,则需执行________。( ) A.link(s)←link(p),link(p)←s B.link(q)←s,link(s)←p C.link(p)←link(s),link(s)←p D.link(p)←s,link(s)←q 3.在非空双向循环链表中由 q 所指的那个链结点前面插入一个由 p 指的链结点的动作对应的语句依次 为:rlink(p)←q , llink(p)←llink(q) , llink←p, _________。 (空白处为一条赋值语句) A.rlink(q)←p B.rlink(llink(q)←p C.rlink(llink(p))←p D.rlink(rlink(p)←p 4.为了节省存储空间,将 n 阶对称矩阵 A 中包括主对角线元素在内的下三角部分的所有元素按 照行序为主序方式存放在一维数组 B[1:n(n-1)/2]中,对任意下三角部分的元素 aij(i≥j)在 B
第 1 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

的下标 k 是 ( ) A.i(i-1)/2+j B.(i(i-1))/2+j C.i(i+1)/2+j B.(i(i+1))/2+j 5.某堆栈的输入序列为 a,b,c,d,下面的四个序列中,__________不可能是它的输出序列。( ) A.a,c,b,d B.b,c,d,a C.d,c,a,b D.c,d,b,a 6.若非空队列采用链式存储结构,front 和 rear 分别为队头元素与队列尾元素的指针,删除此时队列的 一个元素的操作时依次执行 p←front,_________________ ,call RET(P)。( ) A.front←link(rear) B.rear←link(p) C.rear←link(front) D.front←link(p) 7.中缀表达式 A-(B+C)*D/E 的后缀形式是_________________。( ) A.ABC+-D*E/ B.ABC+D*-E/ C.ABC+D-*E/ D.ABC+D*E/8.广大义表 A=((),(a),(b,(c,d)))的长度为 ( ) A.2 B.3 C.4 D.5 9.在初始为空的杂凑表中依次插入关键字序列(MON, TUE, WED, THU, FRI, SAT, SUN), 杂凑函数为 H(k)=i MOD 7,其中,i 为关键字 k 的第一个字母在英文字母表中的序号,地址值域为[0:6],采用线性再散列法 处理冲突。插入后的杂凑表应该如________________所示。( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON 10.从未排序序列中选择一个元素,该元素将未排序序列分成前后两个部分,前一部分中所有元素都小于 等于所选元素。后一部分中所有元素都大于等于所选元素,而所选元素处在排序的最终位置。这种排序方 法称为_____________排序法。( ) A.插入 B.谢尔 C.快速
第 2 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

D.堆积 三、填空题 (每小题 2 分,共 20 分) 1.已知具有 n 个元素的一维数组采用顺序存储结构,每个元素占 k 个存储单元,第一个元素的地址为 LOC(a1),那么,LOC(ai)=___________________。 2.若一棵二叉树有 10 个叶结点,则该二叉树中度为 2 的结的点个数为______________。 3.具有 n 个结点的非空二叉排序树的最小深度为_______________。 4.深度为 h 且有_______________个结点的二叉树称为满二叉树。(设根结点处在第 1 层)。 5.二叉树的前序遍历序列为 A,B,C,E,F,D,G,H,中序遍历序列为 A,E,C,F,B,G,D,H,其后 序遍历序列为__________________。 6.已知序列(34,76,45,18,26,54,92,65,),按照逐点插入法建立一棵二叉排序列树,该树的深 度是__________________。 7.一个不带有权的有向图采用邻接矩阵存储方法,其邻接矩阵是一个__________________。 8.带权连通图 G=<V,E>,其中 V={v1,v2,v3,v4,v5,},E={(v1,,v2)7,(v1,v4)6,(v1,v4)9, (v2,v3)8,(v2,v4)4,(v2,v5)4,(v3,v4)6,(v4,v5)2,(注:顶点偶对右边的数据为边上的权值),G 的 最小生成树的权值之和为__________________ 。 9.在线性表中采用折半查找法(二分查找法)查找一个数据元素,线性表中元素应该按值有序,并且采 用______________存储方法。 10.若对序列(49,38,65,97,76,13,27,50)采用选择排序法排序,则第三趟结束后序列的状态是 ___________________。 四、问题求解题 (每小题 10 分,共 20 分) 1.已知 AOE 网为 G=(V,E),其中, V ={v1,v2,v3,v4,v5,v6,v7}, E = {a1,a2,a3,a4,a5,a6,a7,a8,a9,a10}, a1:(v1,v2)3,a2:(v1,v3)2,a3:(v2,v4)1,a4:(v2,v5)8,a5:(v3,v4)3, a6:(v3,v6)7,a7:(v4,v5)4,a8:(v4,v6)2,a9:(v5,v7)9,a10:(v6,v7)6; (注:顶点偶对的右括号下方的数据表示该边上的权值)。e[i]与 l[i]分别表示活动 a1 的最早开始时间 与最晚开始时间,请分别求出 e[i]与 l[i](1≤i≤10),填入下面的方格中。 e[1:10] l[1:10] 2.若对序列(76,38,65,13,97,27,50,49)采用堆积排序法(按照值的大小从小到大)进行排序,请 分别在下表中写出每一趟的结果: 原始序列 76 38 65 13 97 27 50 49 第 1 趟结果 第 2 趟结果 第 3 趟结果 第 4 趟结果 第 5 趟结果 第 6 趟结果 第 7 趟结果 第 8 趟结果 五、算法题 (共 25 分)
第 3 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

1.已知长度为 n 的线性表 A 采用顺序存储结构,并且元素按值大小非递减排列,下面的算法删除线性表 中多余的值相同的元素。请在算法的空白处填入适当内容,使之能够正常工作。(10 分) procedure DEL (A,n) i←1 while ____________ do if (A[i]≠A[i+1] then i←i+1 else // 查找满足条件的元素 // [ for _________ do A[j-1]←A[j] end // 删除第 i+1 个元素 (满足条件的元素) // ______________ ] // 修改线性表的长度 // end end 2.已知非空线性链表的链结点的构造为| date | link |,第一个链结点的指针为 list,下面的算法删除 链表的第 i 个结点(设 i>0) 。请在算法的空白处填入适当内容,使之能够正常工作。 (15 分) procedure DEL (list,i,item) _____________ // 给变量 q 赋初值 // if (i=1) then list←link(q) // 删除第一个链结点 // else [ for j←1 to ______________ do r←q q←link (q) if _________ then [ call ERROR (i 超过链表的长度!’) return ] end if // r 与 q 分别指向第 i-1 个与第 i 个链结点 // _____________ ] // 删除第 i 个链结点 // call RET(q) // 删除被删除链结点的空间 end

第 4 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

第一章 课堂练习
1.1 判断题(在你认为正确的题后的括号中打√,否则打 X)。 (1)程序与算法没有区别。 ( ) (2)程序设计框图就是一种图形化的算法。 ( ) (3)采用程序设计语言编写的程序也是算法。 ( ) (4)一个算法可以没有输入,但不能没有输出。 ( ) (5)顺序存储结构通过数据元素的地址直接反映数据元素间的逻辑关系。 ( ) (6)链式存储结构通过指针间接地反映数据元素之间的逻辑关系。 ( ) (7)数据的存储结构通常只有顺序存储结构与链式存储结构两种。 ( ) (8)具有相同逻辑结构的数据可以采用不同的存储结构。 ( ) (9)逻辑结构不相同的数据应该采用不同的存储结构。 ( ) (10)算法分析的前提是算法的时空效率高, ( ) 1.2 填空题。 (1)“数据结构”课程研究的主要内容包括——、——和——三个方面。 (2)一般情况下,算法独立于具体的——,与具体的程序设计语言——。 (3)一个完整的算法应该具有——、——、——、——和——五个特性。 (4)数据的逻辑结构可以分为——和——两大类。 (5)除了顺序存储结构与链式存储结构之外,数据的存储结构通常还有——和散列结构。 (6)数据的逻辑结构是指——,而存储结构是指——。 (7)逻辑上相邻的数据元素在物理位置上也相邻是——存储结构的特点之一。 (8)为了实现随机访问,线性结构应该采用——存储结构。 (9)链式存储结构的主要优点是——。 (10)算法分析主要从——和——这两个方面对算法进行分析。 1.3 通常说数据结构是一个二元组(D,R),其中 D,R 分别代表什么? 1.4 何谓数据的逻辑结构?何谓数据的存储结构?两者有何联系?

历年试题
1.在数据结构中,数据的逻辑结构可以分成( )



A.内部结构和外部结构 B.线性结构和非线性结构 C.紧凑结构和非紧揍结构 D.动态结构和静态结构 2.下列说法正确的是( ) A.数据是数据元素的基本单位 B.数据元素是数据项中不可分割的最小标识单位 C.数据可由若干个数据元素构成 D.数据项可由若干个数据元素构成 3.数据结构的基本任务是( ) A.逻辑结构和存储结构的设计 B.数据结构的运算实现 C.数据结构的评价与选择 D.数据结构的设计与实现 4.在一个具有 n 个结点的有序单链表中插入一个新结点,并使插入后仍然有序,则该操作的时间复杂性 量级为( )
第 5 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构
2

A.O(1) B.O(n) C.O(nlog2n) D.O(n ) 5.若结点的存储地址与其关键字之间存在某种映射关系,则称这种存储结构为( ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 6、选出正确的表述 (1)顺序存储方式只能用于存储线性结构。 (2)顺序存储方式的优点是存储密度大, 且插入、删除运用算效率高。 (3)链表的每个结点中都恰好包含一个指针。 (4)散列法存储的基本思想是由关键码的值决定数据的存储地址。 (5)散列表的结点中只包含数据元素自身的信息, 不包含任何指针。 (6)负载因子 (装填因子) 是散列法的一个重要参数, 它反映散列表的装满程度。 (7)栈和队列的存储方式既可是顺序方式, 也可是链接方式。 (8)用二叉链表法 (llink -- rlink法) 存储包含n 个结点的二叉树, 结点的2n个指针区域中有n+1 个为空指针。 (9)用相邻矩阵法存储一个图时, 在不考虑压缩存储的情况下, ?所占用的存储空间大小只与图中结点 个数有关, 而与图的边数无关。 (10)邻接表法只能用于有向图的存储,而相邻矩阵法对于有向图和无向图的存储都适用。 7.表示逻辑关系的存储结构可以有四种方式,即顺序存储方式、链式存储方式、_______________和散列 存储方式。 8.下列程序段的时间复杂度为________________。 product = 1; for (i = n;i>0; i--) for (j = i+1; j<n; j++) product *=j; 9.文件上的两类主要操作为________________和________________。 10.文件的基本运算包括______________和修改两类。 11.下列程序段的时间复杂性量级是_____________。 for (i=1;i<n; i++) for (j=1; j<i; j++) t=t+1; 12.若一个算法中的语句频度之和为 T(n)=3720n+4nlogn,则算法的时间复杂度为________。

第二章

课后辅导

例 2.1 已知长度为 n 的非空线性表 A 采用顺序存储结构,表中数据元素按值的大小非递减排列,请写出 删除该线性表中值相同的多余元素的算法。7654321 7654321 算法思想比较简单,只需从表的第一个数据元素开始到最后那个数据元素,反复做以下动作:比较相 邻的两个数据元素是否相同,若相同,则删除其中一个;若不相同,则比较下一对相邻元素。算法如下: voidDELETEITEM1(ElemTypeA[],int n)) { int j,i=0; while(i<n-1)
第 6 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

if (A[i]!=A[i+1]) /x 若相邻两个元素不相同。/ i++; else{ /*若相邻两个元素相同,则删除其中一个*/ for ( j=i++;i<n;j++) A[j-1]=A[j]; n--; /x 表长减 1 x/ } } } 2 上述算法的时间复杂度为 O(n )。对算法进行改进,得到一个时间复杂度为 O(n)的 算法不是很困难。这里,设置两个整型变量 i 与 k,它们的初值分别为 1 与 0。若在比较 过程中发现 A[i]与 A[k]不同,则先将 k 后移一个位置,然后将 A[i]送到 A[k]的位置上; 若 A[i]与 A[k]相同,只是将 i 后移一个位置。当表中所有元素都处理完毕时,k+1 正好 是删除多余元素以后线性表的长度。 改进后的算法如下: voidDELETEITEM2(ElemTypeA[],int &n) { int k,i; if(n>1) { k=0; for(i=1;i<n;i++) if(A[i]!=A[k]) /x 若 A[i]与 A[k]不相同时。/ A[++k]=A[i]; n=k+1; /。得到删除以后的表长。/ } } 14.将两个按值有序的非空线性链表合并为一个按值有序的线性链表 设 lista 与 listb 分别为 两个有序链表第一个链结点的指针。将这两个有序链表合并 为一个有序链表,其第一个链结点的指针为 listc。 这里,只需设置三个指针 p,q 和 r,其中,p 和 q 分别指向链表 lista 和链表 listb 当前待比较插入 的链结点,而 r 指向链表 listc 中当前最后那个链结点。然后不断地比较 p 与 q 所指的链结点的数据域值,若 p->data < q->data,则将 p 指的链结点链接到 r 所指的链结点之后,否 则将 q 指的链结点链接到 r 所指的链结点之后。当其中一个链表为空时,只 需将另一个链表中剩余的链 结点都依次链接到 r 所指的链结点之后即可。初始时,让 listc 指向 lista 和 listb 所指向的链结点中值小的那一个链结点。 LinkListMERGELIST(LinkListlista,LinkListlistb) { LinkList listc,p,q,r; if(lista->dada<=listb->data){ listc=lista; r=lista; p=lista->link; } else{
第 7 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

listc=listb; r=listb; q=listb->link; } /x listc 指向 lista 和 listb 所指结点中值小者 x/ while(p!=NULL&&q!=NULL){ if(p->data<=q->data){/x 若当前 p 所指结点的值不大于 q 所指结点的值 x/ r->link=p; /y 将 p 所指结点链接到 r 所指结点之后 x/ r=p; p=p->link; } else{ r->link=q; /。将 q 所指结点链接到 r 所指结点之后‘/ r=q; q=q—>link; } } r->link=p?p=q; /x 插人剩余链结点 x/ return(listc); /x 返回合并后的链表第一个链结点地址 x/ } 若两个链表的长度分别为 n 与 m,则上述算法的时间复杂度为 O(n 十 m)。在合并两 个链表为一个链表时不需要另外建立新链表的链结点空间,只需将给定的两个链表中的 链结点之间的链接关系解除,重新按照元素值的非递减关系将所有链结点链接成为一个 链表即可。 例 2.5 约瑟夫(Josephu)问题 已知 n 个人(不妨以编号 1,2,3,?,n 分别表示)围坐在一张圆 桌周围。从编号为 k 的人开始报数,数到 m 的那个人出列,他的下一个人又从 1 开始报数,数到 m 的那个 人又出列,依此规则重复下去,直到圆桌周围的人全部出歹,J。 例如,当 n:8,m’4,k 二 3 时,出列的顺序依次为 6,2,7,4,3,5,1,8。 解决约瑟夫问题可以利用多种数据结构,但比较简单和自然的方法是利用一个具有 n 个链结点、且不 带头结点的循环链表。将圆桌周围的每一个人对应着该链表中的一个链结点,某个人出列相当于从链表中 删除一个链结点。下面的算法就是在该循环链表中不断地报数,不断地删除一个链结点,直到循环链表中 还剩一个链结点时游戏结束。整个算法可以分为三个部分: (1)建立一个具有 n 个链结点且无头结点的循环链表; (2)确定第一个报数点的位置; (3)不断地从链表中删除一个链结点,直至链表中还有一个链结点。

习 题

2.1

判断题(在你认为正确的题后的括号中打√,否则打 X)。 (1)空线性表的特征是表中数据元素都未赋值。 ( ) (2)线性表的顺序存储结构必须占用一片地址连续的存储单元。 ( ) (3)用一维数组存储线性表时,表中第 i 个元素存放在下标为 i 的数组元素中。 (4)采用顺序存储结构的线性表又称为顺序表。 ( )
第 8 页 共 63 页

(

)

济南铁道职业技术学院

专升本辅导教材

数据结构

(5)—个数据元素的地址是指该元素占用的若干存储单元的第一个单元的地址。 ( ) (6)线性表占用的存储单元的数量与表中数据元素的类型有关。 ( ) (7)线性表的顺序存储结构要比链式存储结构节省存储空间。 ( ) (8)线性表的链式存储结构要比顺序存储结构节省存储空间。 ( ) (9)若线性表采用顺序存储结构,线性表的长度等于表中元素的个数与每个元素所占内存单元之乘积。 ( ) (10)若线性表采用顺序存储结构,每个数据元素占用 4 个存储单元,第 12 个数据元素的存储地址为 144 则第 1 个数据元素的存储地址是 101。 ( 100 ) (11)在长度为 n 的顺序表的第 i 个位置插入一个数据元素,i 的合法值为 1≤i≤N。 ( ) (12)删除长度为 n 的顺序表的第 i 个数据元素,i 的合法值为 1≤i≤n。 ( ) (13)在长度为 n 的顺序表中插入一个数据元素的时间复杂度为 O(n)。 ( ) (14)线性表的链式存储结构不必占用地址连续的存储空间。 ( ) (15)链表中的每个链结点占用的存储空间不必连续。 ( ) (16)一个链结点的地址是指该链结点占用的若干存储单元的第一个单元的地址。 ( ) (17)非空线性链表的最后那个链结点的指针域不能为空,应该存放 NULL。 ( ) (18)所谓空链表是指没有任何链结点的链表。 ( ) (19)任何一个链表都可以根据需要设置一个头结点。 ( ) (20)每个链表的前面都必须设置一个头结点。 ( ) (21)线性链表(单向链表)中的每个链结点只有后继结点,没有前驱结点。 ( ) (22)一个空的链表不占用任何存储空间。 ( ) (23)若指针变量 list 指向一个空链表,则 list 中什么也没有。 ( ) (24)无论出现在算法的什么地方,符号 p->data 表示的意思都一样。 ( ) (25)在算法中,符号 p->link 表示 p 所指的下一个链结点的地址。 ( ) (26)删除非空线性链表的第一个链结点只需执行语句 list=list->link。 ( ) (27)循环链表的最后那个链结点的指针域中存放着链表最前面那个结点的地址。 ( ) (28)设置一个指针变量,它可以遍历整个循环链表。 ( ) (29)双向链表的头结点指针要比线性链表的头结点指针占用更多的存储空间。 ( ) (30)在链结点数目相同的前提下,双向链表占用的空间是线性链表的 2 倍。 ( ) 单项选择题。 (1)一个顺序表所占用的存储空间大小与——无关。 A.表的长度 B.元素的存放顺序 C.元素的类型 D。元素中各字段的类型 (2)设存储分配是从低地址到高地址进行的。若每个元素占用 4 个存储单元,则某元素的地 址是指它所占用的单元的 A.第 1 个单元的地址 B.第 2 个单元的地址 C.第 3 个单元的地址 n 第 4 个单元的地址 (3)若线性表采用顺序存储结构,每个元素占用 4 个存储单元,第 1 个元素的存储地址为 100, 则第 12 个元素的存储地址是. 。 A.112 B.144 C.148 0.412 (4)若长度为 n 的线性表采用顺序存储结构,在表的第 i 个位置插入一个数据元素,i 的合法值 应该是——。 A.i>O B.i≤n C.1≤i≤n D.1≤i≤n+1 (5)若长度为 n 的非空线性表采用顺序存储结构,删除表的第 i 个数据元素,i 的合法值应该是 A.i>O B.i≤n C.1≤i≤n D。1≤i≤n 十 1 (6)若长度为 n 的非空线性表采用顺序存储结构,删除表的第 i 个数据元素,首先需要移动表
第 9 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

中——个数据元素。 A.n-i B.n+i C.n-i+l D.n-i-1 (7)若长度为 n 的线性表采用顺序存储结构,在表的第 i 个位置插入一个数据元素,需要移动 表中——个元素。 。 A.i B.n+i C.n-i+l D.n-i-1 (8)若频繁地对线性表进行插入和删除操作,该线性表应该采用——存储结构。 A.散列 B.顺序 C.链式 D.索引 (9)链表中所占用的存储单元地址一定是 。 A.无序的 B.连续的 C.不连续的 D.部分连续的 (10)链表中的每一个链结点所占用的存储单元——。 A.不必连续 B.一定连续 C.部分连续 D.连续与否无所谓 (11)与单链表相比,双向链表的优点之一是 。 A.插入、删除操作更简单 B.可以进行随机访问 C.可以省略头结点指针 D.顺序访问相邻结点更灵活 (12)若 list 是某带头结点的循环链表的头结点指针,则该链表最后那个链结点的指针域中存 放的是——。 A.1ist 的地址 B.1ist 的内容 C.1ist 指的链结点的值 D.链表第一个链结点的地址 (13)若 list 是某带头结点的循环链表的头结点指针,当 p(p 与 list 同类型)指向链表的最后那 个链结点时,——。 A.该结点的指针域为空 B.p 为空 C.p 的内容与头结点的内容相同 D.该链结点指针域内容与 list 的内容相同 (14)若 listl 和 list2 分别为一个单链表与一个双向链表的第一个结点的指针,则——。 A.1ist2 比 listl 占用更多的存储单元 B.1istl 与 list2 占用相同的存储单元 C.1istl 和 list2 应该是相同类型的指针变量 D.双向链表比单链表占用更多的存储单元 (15)在表达式中,符号 p->link 表示——。 A.p 所指的链结点的指针域(位置) B.p 所指的链结点的指针域的内容 C.p 所指的链结点的下一个链结点的地址 D.p 所指的链结点的下一个链结点的地址(出现在表达式中) (16)在一个具有 n 个链结点的线性链表中查找某一个链结点,若查找成功,需要平均比较 ——个链结点。 A.n B.n/2 C.(n+1)/2 D.(n-1)/Q (17)从一个具有 n 个链结点的有序线性链表(即链结点按照数据域值有序链接)中插入一个 新的链结点,并且仍然保持链表有序的时间复杂度为——。 A.O(1) B.O(n) C.O( n(2) ) D.O( log2(n) ) (18)给定具有 n 个元素的顺序表,建立一个有序线性链表的时间复杂度为——。 A.O(1) B.O(n) C.O( n(2) ) D.O( log2(n) ) (19)在非空线性链表中由 p 所指的链结点后面插入一个由 q 所指的链结点的过程是依次执 行——。 A.q->link=p;p->link=q; B.q->link=p->link;p->link=q; C.q->link=p->link;p=q; D.p->link=q;q->link=p; (20)若删除非空线性链表中由 p 所指的链结点的直接后继链结点的过程是依次执行 ________.
第 10 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

A.r=p->link;p->link=r;free(r); B.r=p->link;p->link=r->link;free(r); C.r=p->link;p->link=r->link;free(p); D.p->link=p->link->link;free(p); (21)在非空双向循环链表中由 q 所指的链结点后面插入一个由 p 所指的链结点的动作依次 为:p->llink=Q;p->rlink=q->rlink;q->rlink=p;——。(空白处为一条赋值 语句) A.q->llink=p B.q->rlink->llink=p C.p->fiink->llink=p D.p->llink->llink=p (22)在非空双向循环链表中由 q 所指的那个链结点前面插入一个 p 所指的链结点的动作对 应的语句依次为:p->rlink=Q;p->llink=q->llink;q->[1ink=p;——。(空白 处为一条赋值语句) A.q->rlink=p; B.q->llink->rlink=p; C.p->rlink->rlink=p; D.p->llink->rlink=p; (23)在包含有 1000 个数据元素的线性表中实现如下四个操作,所需要的执行时间最长的是 一O A.线性表采用顺序存储结构,在第 10 个元素后面插入一个新的元素 B.线性表采用链式存储结构,在第 10 个元素后面插入一个新的元素 C.线性表采用顺序存储结构,删除第 990 个元素 D.线性表采用链式存储结构,删除 p 所指的链结点 2.3 填空题。 (1)顺序表是一种——线性表。 (2)在程序设计中,描述线性表的顺序存储结构一般都用——。 (3)在——情况下,删除线性表中一个数据元素平均要移动表中近一半的元素。 (4)在顺序表的——插入一个新的数据元素不必移动任何元素。 (5)若长度为 n 的线性表采用顺序存储结构,在其第 i 个位置(1≤i≤n+1)插入一个新的数据 元素,当不溢出时,首先——,然后——,最后——。 (6)若长度为 n 的线性表采用顺序存储结构,删除其第 i 个元素(1≤i≤n),首先——,然 后——。 (7)若长度为 n 的线性表采用顺序存储结构,插入或删除一个元素的时间复杂度为——。 (8)若某线性表采用顺序存储结构,每个元素占 4 个存储单元,首地址为 100,则第 12 个元素 的存储地址为——。 (9)线性表的链式存储结构主要包括——、——和——三种形式。 (10)线性表的顺序存储结构是通过——来直接反映数据元素之间的逻辑关系,而链式存 储结构则是通过——间接反映数据元素之间的逻辑关系。 (11)根据——的多少,可以将链表分为线性链表(单链表)与双向链表。 (12)若对线性表进行的操作主要不是插入和删除,则该线性表宜采用——存储结构,若 频繁地对线性表进行插入和删除操作,则该线性表宜采用——存储结构。 (13)删除由 list 所指的线性链表的第一个链结点是执行操作——。 (14)删除非空线性链表中由 q 所指的链结点(其直接前驱结点由 r 指出)的动作是执行语句 ——和——。 (15)在线性链表中由 q 所指的链结点后面插入一个地址为 p 的新结点的过程是依次执行操 作——和——。 (16)若 p 为指向循环链表中某链结点的指针变量,判断循环链表是否只有一个链结点的标志
第 11 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

是——。 (17)删除非空双向链表中由 q 所指的链结点的过程是执行语句——和——。 (18)在具有 n 个链结点的链表的已知位置插入一个链结点的时间复杂度为——。 (19)在具有 n 个链结点的链表中查找一个链结点的时间复杂度为——。 (20)一元多项式 f(x)二 9x1’—4x8+3x—5 的线性链表表示为——。 2.4 已知长度为 n 的线性表 A 采用顺序存储结构,请写一算法,找出该线性表中值最小的数据元素。 2. 已知长度为 n 的线性表 A 采用顺序存储结构, 5 请写出逆转该线性表的算法, 即由 A 二(al, a2, ?, An-l,An)产生 A':(An-1,An,?,A1,A2),要求在逆转过程中用最少的附加空间(即用尽可能少的辅助 变量)。 2.6 已知线性表 A 的长度为 n,并且采用顺序存储结构,请写一算法,删除该线性表中所有值为 d 的 数据元素,并讨论算法的时间复杂度。 2.7 已知长度为 n 的线性表 A 采用顺序存储结构,并且每个数据元素均为一个无符号整数,请写一算 法,删除线性表中的所有奇数。 2.8 已知长度为 n 的线性表 A 采用顺序存储结构,请写一时间复杂度为 O(n)的算法,该算法删除线性 表中原来序号为奇数的那些数据元素。 2. 已知长度为 n 的线性表 A 采用顺序存储结构, 9 写一算法, 删除表中重复出现的所有数据元素 要 求:剩余元素的相对位置保持不变。 2.10 已知长度为 n 的线性表 A 采用顺序存储结构,并且元素按值的大小非递减排列,请写一算法, 在线性表中插入一个新的数据元素让 em,要求插入以后线性表中元素仍然保持按值的大小非递减排列。 2.11 已知长度为 n 的线性表 A 采用顺序存储结构,写一算法,删除所有值大于 x 且小于 y 的数据元 素。 2.12 请写一算法,通过键盘输入一系列数据元素,建立一个长度为 n、且不包含重复元素的线性表 A。 这里,设线性表 A 采用的存储结构为顺序存储结构,并且假设空间足够。 2。13 已知线性表 A 与线性表 B 的长度分别为 n 与 m,并且都采用顺序存储结构,写一算法,在线性表 A 的第 i 个位置插入线性表 B。约定:不考虑存储空间溢出问题。 2.14 已知非空线性链表的第一个链结点的存储地址为 list,写出删除该链表第 i 个链结点的算法。 2. 已知非空线性链表第一个链结点的存储地址为 1ist, 15 试写出删除链表中从第 i 个链结点开始的(包 括第 i 个链结点本身)连续 k 个链结点的算法。 2.16 已知线性链表第一个链结点的存储地址为 1ist,写一算法,把该链表中数据域值为 d 的所有链 结点的数据域值修改为 p。 2.17 已知线性链表第一个链结点指针为 list,写一算法,删除链表中数据域值最大的那个链结点。 2.18 已知线性链表第一个链结点指针为 list,写一算法》 断该链表是否是有序链表(即链结点是 ,j 否按照数据域大小链接),若是,算法返回 1,否则返回—1。 2.19 已知线性链表第一个链结点指针为 1ist,写一算法,交换 p 所指链结点与其下一个链结点的位 置(设 p 指向的不是链表最后那个链结点)。 2.20 已知非空线性链表第一个链结点由 list 指出,请写一算法,将链表中数据域值最小的链结点移 到链表最前面。 2.21 已知非空线性链表第一个结点的指针为 list,试编写一算法按递减次序打印各链结点数据域的 内容(提示:在链表中打出最大值结点,打印之后将其删除。反复执行,直到链表为空时为止)。 2.22 已知一个不带头结点也无头指针变量,并且长度大于 1 的循环链表,试写一算法,删除 p 所指 链结点的直接前驱结点。 2.23 已知带有头结点的循环链表中头结点的指针为 list,试写出删除并释放数据域内容为 x 的所有 结点的算法。 2.24 已知线性链表第一个链结点的指针为 list,试写一算法,删除数据域值相同的多余结点,即:
第 12 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

若链表中有多个结点具有相同的数据域值,只保留其中一个结点,其余结点均从链表中的最后删去, 使得到的链表中所有结点的数据域值都不相同。 2.25 设线性表 X=(x1,x2,?,Xn)与 Y=(yl,y2,?,ym)都采用链式存储结构(两个链表第一个结 点的指针不妨用 X 与 Y 分 9U 表示)。试写一个算法归并这两个线性链表为一个线性链表,使 ((x1,Y1,x2,y2,?,xm,Ym,Xm+1,?,Xn) 当 m≤n 时 ((x1,Y1,x2,y2,?,xn,yn,yn+1,?,ym) 当 m>n 时 2.27 试写出将一个线性链表(第一个结点的存储地址为 list)分解为两个循环链表,并将两个循环链 表的长度存放在各自的头结点的数据域中的算法。 分解规则:若线性链表中某一链结点属于第一个循环链表,则下一个链结点就属于第二 个循环链表;反之,若线性链表中某一个链结点属于第二个循环链表,则下一个链结点就属于第一个 循环链表。 2. 28 设 A 与 B 分别为两个带有头结点的有序循环链表(所谓有序是指链结点按数据域值大小链接, 这里, 不妨按数据域值从小到大链接),lista 和 listb 分别为两个链表的头结点指针。请写出将这两个链表合并 为一个带头结点的有序循环链表的算法。 2.29 已知循环链表头结点指针 list,请编写一个能逆转链表方向的算法。 2.30 写一算法,先从键盘输人 n 个整型数,建立一个带有头结点的双向循环链表,然后按照与输入相 反的次序依次输出这 n 个整型数。 2.31 在非空双向循环链表中由 q 所指的结点后面插入一个数据信息为 item 的新结点的算法如下: voidINSERTD(DLinkListq,datatypeitem) { DLinkList p; p:(DLinkList)malloc(sizeof(DNode)); /*申请一个新的链结点*/ p->data=item; p->llink=q; p->rlink=q->rlink; q->rlink=p; 请在算法的方框中填上必要的动作(一条语句)。 2.32 有人说线性表的顺序存储结构比链式存储结构的存储空间开销要小,也有人说线性表的链式存储 结构比顺序存储结构的存储空间开销要小,你是如何看待这两种说法的?请说明你的看法。

第二章 历年试题
1.在线性表的下列存储结构中,读取元素花费时间最少的是( ) ) A.单链表 B.双链表 C.循环链表 D.顺序表 2. 顺序存储的线性表 1,a2,?,an) (a ,在任一结点前插入一个新结点时所需移动结点的平均次数为 ( A.n B.n/2 C.n+1 D.(n+1)/2 3.在长度为 n 的顺序表的第 i(1≤i≤n+1)个位置上插入一个元素,元素的移动次数为( ) A.n-i+1 B.n- i C.i D.i-1 个元素。 一、选择题 1.在线性表的下列存储结构中,读取元素花费时间最少的是( A.单链表 B.双链表 C.循环链表
第 13 页 共 63 页

4. 在顺序存储的线性表 1,a2?,n) (a a 中的第 i (1≤i≤n)个元素之前插入一个元素, 则需向后移动_________

) D.顺序表

济南铁道职业技术学院

专升本辅导教材

数据结构

2.顺序存储的线性表(a1,a2,?,an ),在任一结点前插入一个新结点时所需移动结点的平均次数为 ( ) A.n B.n/2 C.n+1 D.(n+1)/2 3.在长度为 n 的顺序表的第 i(1≤i≤n+1)个位置上插入一个元素,元素的移动次数为( ) A.n-i+1 B.n- i C.i D.i-1 4.在顺序存储的线性表(a1,a2?,an)中的第 i (1≤i≤n)个元素之前插入一个元素,则需向后移动 _________个元素。 5.在以单链表为存储结构的线性表中,数据元素之间的逻辑关系用( A.数据元素的相邻地址表示 C.指向后继元素的指针表示 B.数据元素在表中的序号表示 D.数据元素的值表示 ) )

6.设 p 指向单链表中的一个结点,s 指向待插入的结点,则下述程序段的功能是( s -> next = p -> next; p -> next = s; t = p -> data; p -> data = s -> data; A.结点*p 与结点*s 的数据域互换 B.在 p 所指结点的元素之前插入元素 C.在 p 所指结点的元素之后插入元素 D.在结点*p 之前插入结点*s 7.在线性表的下列存储结构中,读取元素花费时间最少的是( A.单链表 C.循环链表 B.双链表 D.顺序表 ) s ->data = t;

8.将一个头指针为 p 的单链表中的元素按与原单链表相反的次序存放,则下列算法段中的空白处应为: q=NULL; while (p!=NULL) { ( ) } p=q; A. r =q; q=p; p=p -> next; q -> next=r; B.q=p; r=q; p=p -> next; q -> next=r; C.r=q; p=p -> next; q=p; q -> next=r; D.q=p; p=p -> next; r=q; q -> next=r; 9.对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 10.设单链表中结点的结构为 typedef struct node { //链表结点定义 ElemType data; //数据 struct node * Link; //结点后继指针 } ListNode; (1) 已知指针 p 所指结点不是尾结点,若在*p 之后插入结点*s,则应执行下列哪一个操作? A. s->link = p; p->link = s; B. s->link = p->link; p->link = s; C. s->link = p->link; p = s;
第 14 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

D. p->link = s; s->link = p; (2) 非空的循环单链表 first 的尾结点(由 p 所指向)满足: A. p->link == NULL; B. p == NULL; C. p->link == first; D. p == first; 二、判断题。 (1) 线性表的逻辑顺序与物理顺序总是一致的。 (2) 线性表的顺序存储表示优于链式存储表示。 (3) 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。 (4) 二维数组是其数组元素为线性表的线性表。 (5) 每种数据结构都应具备三种基本运算:插入、删除和搜索。 三、填空题。 1.已知指针 p 指向单链表中某个结点,则语句 p -> next =p -> next -> next 的作用是________。 2.若链串结点中的指针占 4 个字节,每个字符占 1 个字节,则结点大小为 2 的链串的存储密度为 ________。

3.设某非空双链表,其结点形式为若要删除指针 prior data 所指向的结点,则需执行下述语句段: q->prior->next=q->next; __ _____________。

next

q

4.在如图所示的链表中,若在指针 p 所指的结点之后插入数据域值相继为 a 和 b 的两个结点,则可 用下列两个语句实现该操作,它们依次是________和________。

5.函数中,h 是带头结点的双向循环链表的头指针。 (1) 说明程序的功能; (2) )当链表中结点数分别为 1 和 6(不包括头结点)时, 请写出程序中 while 循环体的执行次数。 int f(DListNode *h) { DListNode *p,*q; int j=1; p=h->next; q=h->prior; while(p!=q && p->prior!=q) if(p->data==q->data)
第 15 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

{ p=p->next; q=q->prior; } else j=0; return j; } 6.下列函数的功能是,对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同 的数据元素)进行如下操作:将所有在 Lb 表中存在而 La 表中不存在的结点插入到 La 中,其中 La 和 Lb 分别为两个链表的头指针。请在空缺处填入合适内容,使其成为一个完整的算法。 void union (LinkList La, LinkList Lb) { //本算法的功能是将所有 Lb 表中存在而 La 表中不存在的结点插入到 La 表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd) { if (pa -> data <pb -> data) { { pre = pa; pa = pa -> next;} (1) pre = pb; pb = pb -> next; (2) } else {q = pb; pb = pb -> next; free (q); } } if (pb) (3) } 四、程序设计 1、设某头指针为 head 的单链表的结点结构说明如下: 分) (6 typedef struct node1 { int data; struct node1*next }node; 试设计一个算法 void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放,即 ; ; ; else if (pa -> data > pb ->data)

第 16 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

第一个结点变成最后一个结点,第二个结点变为倒数第二个结点,如此等等。 2.设某带头结头的单链表的结点结构说明如下: typedef struct nodel { int data; struct nodel*next; }node; 试设计一个算法:void copy(node*head l, node*head 2),将以 head 1 为头指针的单链表复制到一个 不带有头结点且以 head2 为头指针的单链表中。 分) (6 3、 、设带表头结点的双向链表的定义为 typedef int ElemType; typedef struct dnode { //双向链表结点定义 ElemType data; //数据 struct dnode * lLink, * rLink; //结点前驱与后继指针 } DblNode; typedef DblNode * DblList; //双向链表 试设计一个算法, 改造一个带表头结点的双向链表, 所有结点的原有次序保持在各个结点的右链域 rLink 中,并利用左链域 lLink 把所有结点按照其值从小到大的顺序连接起来。 4、阅读以下程序说明和C程序,将应填入程序中(n) 处的字句,写在答卷的对应栏内。 [程序说明] 本子程序利用递归法判别用链表表示的两个非递归链表是否相等. 程序中的非递归列表定义为: ⑴无元素的空列表; ⑵由元素序列组成的一个列表,其中的元素可以是一个字符,?或者是满足本定义的一个列表. 这种列表的一个例子是: S ┌───┐ ┌─┬─┬─┐ ┌─┬─┬─┐ │ ├→┤0 │a│ ├-→┤1│││^│ └───┘ └─┴─┴─┘ └─┴┼┴─┘ ┌──────┘ │ ┌─┬─┬─┐ ┌─┬─┬─┐ └→┤0 │b│ ├→┤0│c │^│ └─┴─┴─┘ └─┴─┴─┘ 列表S由两个元素组成:第一个元素是字符a (标志为0);第二个元素是另一个列*表(标志为1),该元 素又有两个元素组成(标志为0),分别为字符b和字符c. 在两个列表中,若它们的元素个数相等,且表中元素依次相同,则两个列表相等(子程序回答1),否则不 相等(子程序回答0). [程序] typedef struct lnode { int tag; union { char data; struct lnode *dlink; } un; struct lnode *link; } listnode;
第 17 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

int equal(s,t) listnode *s,*t; { int x,res; if(s==t) __(1)__ ; else if( __(2)__ ) if( __(3)__ ) { if(!s->tag) x= __(4)__ ; else x= __(5)__ ; if(x) return (__(6)__); } return(0); } 5、阅读下列函数说明和C代码,将应填入其中__(n)__处的字句写在答卷的对应栏内。 【函数1.1说明】 设链表结点的类型为 typedef struct elem{ int val; struct elem *next; }intNode; 函数merge(int *a,int *b)是将两个升序链表a和b合并成一个升序链表。 【函数1.1】 intNode *merge(intNode *a,intNode *b) { intNode *h=a,*p,*q; while(b) { for (p=h;p && p→val< b→val;q=p,p = p→next); if (p = = h) __(1)__;else __(2)__; q=b;b=b→next; __(3)__; } return h; } 【函数1.2说明】 递归函数dec(int a[],int n)判断数组a[]的前n个元素是否是不递增的。不递增返回1,否则返回0。 【函数1.2】 int dec(int a[],int n) { if (n<=1) __(4)__; if (a[0]<a[1]) return 0; return __(5)__; }

第 18 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

第三章

栈和队列

习题

4.1 判断题(在你认为正确的题后的括号中打√,否则打 X)。 (1)堆栈和队列都是特殊的线性表。 ( ) (2)堆栈和队列都将插入和删除操作限制在表的端点处进行。 ( ) (3)只允许在表的一端进行插入和删除操作的线性表称为堆栈。 ( ) (4)没有元素的堆栈称为空栈,空栈用不着栈顶指针。 ( ) (5)只要堆栈不空,就能任意删除堆栈的元素。 ( ) (6)堆栈允许删除的一端称为栈顶,而栈底元素是不能删除的。 ( ) (7)n 个元素进栈的顺序一定与它们出栈的顺序相反。 ( ) (8)对采用链式存储结构的堆栈进行操作不必判断溢出。 ( ) (9)给出顺序堆栈的栈顶元素位置的指针是一个指针类型的变量。 ( ) (10)判断顺序堆栈是否为空的标志是 top 是否等于 0(top 为栈顶指针)。 ( ) (11)插入和删除操作比较简单是链接堆栈和链接队列的优点之一。 ( ) (12)n 个元素进队的顺序与它们出队的顺序一定是相同的。 ( ) (13)没有任何元素的队列称为空队。空队用不着队头指针与队尾指针。 ( ) (14)元素进出队列一定满足“先进先出”的规律。 ( ) (15)链接队列不存在溢出问题。 ( ) (16)在链接队列中删除一个元素是在链表的最前端进行的。 ( ) (17)采用循环链表作为存储结构的队列称为循环队列。 ( ) (18)堆栈和队列都可以用来解决递归问题。 ( ) (19)堆栈和队列都不适合采用散列存储方法。 ( ) (20)无论是顺序队列还是链接队列,插入、删除操作的时间复杂度都是 O(1)。 ( ) 4.2 单项选择题。 (1)堆栈和队列的共同之处在于它们具有相同的——。 A.逻辑特性 B.物理特性 C.运算方法 D.元素类型 (2)堆栈和队列都是特殊的线性表,其特殊性在于_______。 A.它们具有一般线性表所没有的逻辑特性 B.它们的存储结构比较特殊 C.对它们的使用方法做了限制 D.它们比一般线性表更简单 (3)若 5 个元素的出栈序列为 1,2,3,4,5,则进栈序列可能是——。 A.2,4,3,1,5 B.2,3,1,5,4 C.3,1,4,2,5 D.3,1,2,5,4 (4)某队列初始为空,若它的输入序列为 a,b,c,d,它的输出序列应为——。 A.a,b,c,d B.d,c,b,a C.a,c,b,d D.d,a,c,b (5)当 4 个元素的进栈序列给定以后,由这 4 个元素组成的可能的出栈序列应该有——。 A.24 种 B.17 种 C.16 种 D.14 种 (6)设 n 个元素的进栈序列为 1,2,3,?,n,出栈序列为 p1,p2,p3,?,pn,若 Pi=n,则 B(1≤i<n) 的值——。 A.为 i B.为 n-i C.为 n-i+l D.有多种可能 (7)设 n 个元素的进栈序列为 p1,p2,p3,?,pn,出栈序列为 1,2,3,?,n,若 Pn=l,则 n(1≤i< n) 的值——。 A.为 i B.为 n-i C.为 n-i+l D.有多种可能 (8)若堆栈采用顺序存储结构,正常情况下,往堆栈中插入一个元素,栈顶指针 top 的变化是 ______.
第 19 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

A.不变 B.top=0 C.top-D.top++ (9)若堆栈采用顺序存储结构,正常情况下,删除堆栈中一个元素,栈顶指针 top 的变化是 ______. A.不变 B.top=0 C.top-D.top++ (10)若队列采用顺序存储结构,元素的排列顺序——。 A.与元素的值的大小有关 B.由元素进入队列的先后顺序决定 C.与队头指针和队尾指针的取值有关 n 与作为顺序存储结构的数组的大小有关 (11)“链接队列”这一概念不涉及——。 A.数据的存储结构 B.数据的逻辑结构 C.对数据进行的操作 D.链表的种类 (12)若堆栈采用链式存储结构,栈顶指针为 top,向堆栈插入一个由 p 所指的新结点的过程是依次执行: ——,top=p。 A.p=top B.top=p C.p->link=top D.top->link=p (13)若非空堆栈采用链式存储结构,栈顶指针为 top,删除堆栈的一个元素的过程是依次执行:p=top, ——,free(p)。 A.top=p B.top=p->link C.p=top->link D.p=p->link (14)若队列采用链式存储结构,队头元素指针与队尾元素指针分别为 front 和 rear,向队列中插入一个由 p 所指的新结点的过程是依次执行:——,rear=p。 A.rear=p B.front=p C.rear->link=p D.front->link=p (15)若非空队列采用链式存储结构,队头元素指针与队尾元素指针分别为 front 和 rear,删除队列的一个 元素的过程是依次执行:p=front,——,free(p)。 A.rear=p B.rear=p->link C.rear=p->link D.front=p->link (16)在循环队列中,若 front 与 rear 分别表示队头元素和队尾元素的位置,则判断循环队列队空的条件是 ——。 A.front=rear+1 B。rear=front+1 C.front--rear D.b 叭 t:0 (17)若描述某循环队列的数组为 ClUELIE[M],当循环队列满时,队列中有——个元素。 A.M B.M-1 C.M 十 1 D.M+2 (18)在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出 的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据打印,该缓 冲区应该是一个——结 构。 A.线性表 B.数组 C.堆栈 D.队列 (19)设计一个递归问题的非递归算法通常需要设置——结构。 A.线性表 B.数组 C.堆栈 D.队列 (20)中缀表达式 A-(B+C/D)*E 的后缀形式是——。 A.ABC+D/*E— B.ABCD/+E*— C.AB-C 十 D/E* D.ABC-+D/E* 4.3 填空题。 (1)堆栈和队列的逻辑结构都是——结构。 (2)堆栈的插入和删除操作都是在——位置进行, 而队列的插入操作在——进行, 删除操作在——进行。 (3)对某堆栈执行删除操作时,只有在——情况下,才会将栈底元素删除。 (4)在具体的程序设计过程中,堆栈的顺序存储结构一般是利用一个——描述的,同时还要定义一个整 型变量来——。 (5)若堆栈采用顺序存储结构, 在不产生溢出的情况下往堆栈中插人一个新元素, 首先——, 然后——。 (6)若队列采用顺序存储结构,未溢出时插入一个元素首先——,然后再——。
第 20 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

(7)当堆栈的最大长度难以估计时,堆栈最好采用——存储结构。 (8)递归算法都可以通过设置——机制改写成等价的非递归算法。 (9)中缀形式的算术表达式 A+(B-C)/D*E 的后缀形式为——。 (10)后缀形式的算术表达式 ABCD/-E*+的中缀形式为——。 4.4 已知堆栈采用链式存储结构,初始时为空,请画出 a,b,c,d 四个元素依次进栈以后该堆栈的状态, 然后再画出此时的那个栈顶元素出栈后堆栈的状态。 4.5 若按从左到右的顺序依次读人已知序列{a,b,c,d,e,f,g1 中的元素,然后结合堆栈操作,能得 到下列序列中的哪些序列(每个元素进栈一次,下列序列表示出栈的次序)? {d,e,c,f,b,g,a} {f,e,g,d,a,c,b} {e,f,d,g,b,c,a} {c,d,b,e,f,a,g} 4.6 设有编号 1,2,3,4 的四辆列车,顺序进入一个栈式结构的站台,请写出这四辆列车开出车站的 所有可能的顺序。 4.7 设 STACK[M]为 n(n>2)个堆栈共享。各栈栈顶指针为 top[n],分别指出各栈栈顶元素的位置;栈底 指针为 bot[n+1],分别指出各栈栈底元素的位置。初始时, bop[i]=bot[i]=i*ROUND(M/n—0.5) (i=1,2,....,n) 其中,ROUND()为四舍五人取整函数。请写一算法,该算法向任意指定的第 i 个堆栈插入一个新的元 素 x。仅当 M 个空间全部占用时才产生溢出,并报告相应信息(1≤i≤n)。 4.8 设中缀表达式 E 存放于字符数组中,并以@作为结束标志。请写出判断一个中缀表达式 E 中左、右 圆括号是否配对的算法。 4.9 写出将中缀表达#(a+b)/c-d#变换为后缀表达式的过程中, 每读到一个单词时堆栈的状态(#为中缀表 达式的左、右分界符)。 4.10 已知 Ackerman 函数定义如下:

(1)写出递归算法; (2)利用堆栈写出非递归算法; (3)根据非递归算法,求出 A(:K(2,1)的值。 4.12 已知求两个正整数 m 和 n 的最大公约数的过程可以表达为如下递归函数:

请写出求解该递归函数的非递归算法。m MOD n 表示 m 对 n 取模。 4. 13 假设以数组 Q[M]存放循环队列的元素, 同时设置变量 rear 与 qlen 分别指示循环队列中队尾元素的 位置和队列中元素的个数。 请给出此循环队列的队满条件, 并写出相应的进队与出队算法(在出队算法中要 求返回队头元素)。 4.14 编写一非递归算法,对于给定的十进制整数 n,打印出对应的 r 进制整数(2≤r≤16,r<>10)。

栈和队列
1.栈和队列都是( ) A.限制存取位置的线性结构 C.链式存储的线性结构

历年试题

B.顺序存储的线性结构 D.限制存取位置的非线性结构

2.若数组 s[0..n-1]为两个栈 s1 和 s2 的共用存储空间,且仅当 s[0..n-1]全满时,各栈才不能进行进栈操
第 21 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

作,则为这两个栈分配空间的最佳方案是:s1 和 s2 的栈顶指针的初值分别为(



A.1 和 n+1 B.1 和 n/2 C.-1 和 n D.-1 和 n+1 3.若进栈序列为 a,b,c,则通过入出栈操作可能得到的 a,b,c 的不同排列个数为( ) A.4 B.5 C.6 D.7 4.假设元素只能按 a,b,c,d 的顺序依次进栈,且得到的出栈序列中的第一个元素为 c,则可能得到的出栈 序列为________________,不可能得到的出栈序列为________________。 5.在栈的顺序实现中,若栈不满,则进栈操作可以用下列算法片断实现: _____________; sq -> data[sq -> top]=x; 6.链队列实际上是一个同时带有头指针和尾指针的单链表,尾指针指向该单链表的_____________。 7.如图所示,设输入元素的顺序是 A,B,C,D,通过栈的变换,在输出端可得到各种排列。若输出序 列的第一个元素为 D,则输出序列为_______________。

8.队列中允许进行删除的一端为________________。 9.假设以 S 和 X 分别表示进栈和退栈操作, 则对输入序列 a,b,c,d,e 进行一系列栈操作 SSXSXSSXXX 之后, 得到的输出序列为________。 10、 设有一个顺序栈 S, 元素 s1, s2, s3, s4, s5, s6 依次进栈, 如果 6 个元素的出栈顺序为 s2, s3, s4, s6, s5, s1, 则顺序栈的容量至少应为多少? 11.如图所示,输入元素为 A,B,C,在栈的输出端得到一个输出序列 ABC,求出在栈的输入端所有可 能的输入序列。 分) (5

第四章

数组补充内容

3.3.2 对角矩阵的压缩存储 所谓对角矩阵是指矩阵中的所有非零元素都集中在以主对角线为中心的带状区域中,即除了主对角线 上和直接在主对角线上、下方对称的若干条对角线上的元素之外,其余元素均为零。 下面给出的矩阵 B 就是一个对角矩阵(确切地说是一个三对角矩阵,这里,我们仅以三对角矩阵为例 子)。

第 22 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

三对角矩阵一共有 3n—2 个非零元素。我们可以按照某个原则(或者以行序为主序的分配方式,或者 以列序为主序的分配方式,或者按照对角线的顺序进行分配)将对角矩阵 B 的所有非零元素压缩存储到一 个一维数组 LTB[3n—2]中。这里,不妨仍然以行序为主序的分配方式对 B 进行压缩存储,当 B 中任一非 零元素 Bij 与 LTB[k]之间存在着如下一一对应关系 k=2*i+j-3 时,则有 Bij=LTB[k]。称 LTB[3n—2]为对角 矩阵 B 的压缩存储,如下图所示。

上面讨论的几种特殊矩阵中,非零元素的分布都具有明显的规律,因而都可以被压缩 存储到一个一维数组中,并且能够确定这些矩阵的每一个元素(或非零元素)在一维数组 中的位置。但是,对于那些非零元素在矩阵中的分布没有规律的特殊矩阵(如稀疏矩阵), 则需要寻求其他的方法来解决压缩存储问题。 3.5 稀疏矩阵的十字链表表示 上一节讨论了用三元组表的形式来存储一个稀疏矩阵的方法。但是,在实际应用中,当稀疏矩阵中非 零元素的位置或者个数经常发生变化时,使用三元组表就不太方便了。 本节将介绍稀疏矩阵的另一种表示方法,即十字链表表示。 如何用链表形式来表示一个稀疏矩阵呢?方法之一就是将所有非零元素以行序为主序方式(当然也可以以列 序为主序方式)采用循环链表链接起来。链结点的构造由四个域组成:

其中 i,j 分别表示某一个非零元素所在的行号与列号;value 表示该非零元素的值; link 域用来指向下 一个非零元素所在的链结点,它是一个指针。另外,再设置一个链表头结点,其构造如下:

其中,m,n 分别表示稀疏矩阵的行数与列数;t 为稀疏矩阵非零元素的总个数;link 域用来指向第一 个非零元素对应的链结点。 例如,对于如下一个稀疏矩阵:

若采用行序为主序方式(每行又按列的先后顺序)依次将所有非零元素链接起来,则得到如图 3.4 所示 的一个带有头结点的循环链表。

第 23 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

这种表示方法最明显的一个缺点就是,当要访问某行某列的一个非零元素时,必须从链表的最前面 那个链结点开始进行搜索,其效率之低可想而知。 一个能提高访问效率的方法就是采用十字链表表示。这种方法为稀疏矩阵的每一行设置一个单独的行 循环链表,同样也为每一列设置一个单独的列循环链表。这样,稀疏矩阵中的每一个非零元素同时包含在 两个链表中,即包含在它所在的行链表与所在的列链表中,也就是这两个链表的交汇处。 对于一个 mXn 的稀疏矩阵,分别建立 m 个行的循环链表与 n 个列的循环链表,每个非零元素用一个 链结点来存储。链结点的结构可以设计为

其中,rOW,c01,value 分别表示某非零元素所在的行号、列号和相应的元素值;down 与 right 分别 称为向下指针与向右指针,它们分别用来链接同一列中的与同一行中的某非零元素结点。也就是说,稀疏 矩阵中同一行的所有非零元素是通过 right 指针链接成一个行链表,同一列中的所有非零元素是通过 down 指针链接成一个列链表。而对每一个非零元素而言,它既是某个行链表中的一个链结点,同时又是某个列 链表中的一个链结点,这个非零元素好比处在一个十字路口,故称这种链表表示为十字链表表示法。 作为链表,应该用某种方式能访问表中的第一个结点,为此,对于 m 个行链表,分别设置 m 个行链 表表头结点。表头结点的构造与链表中其他链结点一样,只是令 row 与凹 1 域的值均为 0,right 域指向相 应行链表的第一个链结点。同理,对于 n 个列链表,分别设置 n 个列链表表头结点。头结点结构也同其他 链结点一样,只是令 rOW 与 c01 的值均为 0,down 域指向相应列链表的第一个链结点。另外,通过 value 域把所有这些表头链结点也链接成一个循环链表。 十字链表中的链结点类型可以描述如下: typedefstructnode{ int row,col; union{ ElemType val; struct node'ptr; 1value; struct node 1 right,'down; 1 CNode,xCrossLink; /‘定义十字链表结点类型 x/ 从 m 个行链表的表头结点与 n 个列链表的表头结点的设置情况看到,行链表的头结点只用了 right 域 作为指针,而列链表的头结点只用了 down 域与 value 域,其他域没有使用。因此,可以设想原来的(m+n) 个头结点实际上可以合并成 MAX(m,n)。为此,再设置一个结点作为头结点链表的头结点,不妨称之为 总头结点,其结构如下所示: m t 其中,m,n 分别为稀疏矩阵的行数与列数;t 为非零元素的总个数;1ink 指向头结点链表的第一个头 结点。
第 24 页 共 63 页

n

Link

济南铁道职业技术学院

专升本辅导教材

数据结构

总头结点的类型可以如下描述: typedefstruct{ int m,n,t,nil; CrossLink x link; }HNode,*HLink; /x 定义十字链表总头结点类型 x/ ‘ 综上所述,若给出一个稀疏矩阵 B 如下,则它的十字链表表示如图 3.5 所示。

下面给出创建一个具有 m 行 n 列、有 t 个非零元素的稀疏矩阵的十字链表的算法。 稀疏矩阵用三元组表的形式作为输入。 首先输入稀疏矩阵的行数、 列数以及非零元素总个数(m, t), n, 然后依次读入个三元组。算法中用到了一个辅助数组 hdnode [MAX(m,n)]。其中,hdnode[i]用来分别存放 第 i 列(也是第 i 行)链表的头结点的指针 (1≤i≤MAX(m,n))。 #defineMaxNl00 HLinkMREAD() { HLinkHEAD,p,last,hdnode[MaxN];
第 25 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

iht m,n t,k,i,Current_row, int rrow,ccol,val; scanf("%d%d%",&n,&n,&t); /x 读入矩阵的行、列和非零元素的个数‘/ if(t<=0) return NULL; k=(m>n)?m:n; for(i=0;i<k;i++){ p=(HLink)malloc(sizeof(HNode)); hdnode[i]=p; p->row=0; p->col=0; p->value.ptr=P; p->rlght=p; p->down=p; } /*建立 k 个头结点;初始时第 i 个头结点的地址存放于 hdnode[i-1]中 x/ Current_row=1; last=hdnode[0]; for(i=1;i<=t;i++){ scanf("%d%d%d",&rrow,&ccol,&val); /x 读人一个某非零元素的三元组 x/ if(rrow>current_row){ last—>right=hdnode[Current_row—1]; current_row=rrow; last=hdnode[rrow—1]; } p=(CrossLink)malloc(sizeof(CNode)); /x 申请一个新的链结点空间 x/ p—>row=rrow; p->col=ccol; p—>value.val=val; last->right=p; /x 生成一个新的链结点 x/ last=p; hdnode[ccol—1)->value.ptr->down=p; /‘将新结点链接到相应行链表中,/ kfnode[ccol—1)->value.ptr=p; /x 将新结点链接到相应列链表中,/ ; if(t!=0) last->right:hdnode[current—row—1]; /x 封闭最后——行 x/ for(i=0;i<k;i++) /x 通过 value 域将头结点链接为一条循环链表。/ hdnode[i]->value.ptr->down=hdnode[i];/x 封闭所有列链表 x/ HEAD=(HLink)malloc(sizeof(HNode)); /,申请一个总的头结点 x/ HEAD->m=m; HEAD->n=n; HEAD->t=t; for(i=0;i<k-1;i++) hdnode[i]->value.ptr=nanode[i+1]; if(k==0)
第 26 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

HEAD->value.ptr=HEAD; else{ hdnode[k-1]->value.ptr=HEAD; HEAD->value.ptr=hdnode[0]; return HEAD; }

第四章

广义表

字符串

数组

4.1 单项选择题。 (1)空的广义表是指广义表——。 A.深度为 0 B。尚未赋值 C.不含任何原子元素 D.不含任何元素 (2)广义表中元素分为——。 A.原子元素 B.表元素 C.原子元素和表元素 D.任意元素 (3)广义表的长度是指——。 A.广义表中元素的个数 B.广义表中原子元素的个数 C.广义表中表元素的个数 Di 广义表中括号嵌套的层数 (4)广义表的深度是指——。 久广义表中元素的个数 B.广义表中原子元素的个数 C.广义表中表元素的个数 D.广义表中括号嵌套的层数 (5)在一个长度为 n,包含 m 个原子元素的广义表中,——。 A.m 和 n 相等 B.m 不大于 n C.m 不小于 n D.m 与 n 无关 (6)广义表 A=(( ),(a),(b,(c,d)))的长度为——。 A.2 B.3 C.4 D.5 (7)广义表 A:(( ),(a),(b,(c,d)))的深度为——。 A.2 B.3 C.4 D.5 4.2 有人说,m*n 阶矩阵是一种广义表结构,你认为如何?请说明你的理由。 4.3 请分别写出下列各广义表的长度与深度: (1)A=((a)) (2)B=(a,(b,c,d),e,()) (3)C=(x,((y),B,A)) (4)D=(A,D) 4.6 试写出判断两个广义表是否相等的递归算法。 4.7 根据本章介绍的 m 元多项式的表示方法,试写出一个 m 元多项式相加的算法。 4.1 请回答空串与空格串有何区别。 4.2 两个字符串相等的充分必要条件是什么? 4.3 已知字符串 S 采用链式存储结构,链结点大小为 1。试写出求该串长度的算法。 4.4 已知字符串 S1 与 S2 都采用链式存储结构,链结点大小为 1。试写出判断 S1 与 S2 是否相等的算 法。若 S1 与 S2 相等,算法返回 1 否则返回 0。 4.5 设串 S,S1,S2 分别采用顺序存储结构,长度分别为 len,lenl,len2。试写一算法,用串 S2 替 换串 S 中的子串 S1。 4.6 设串采用链式存储结构,链结点大小为 1。试写出删除 S 中从第 i 个字符开始连续 k 个字符的算 法。
第 27 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

4. 在字节编址的机器中, 7 字符串 S1 与 S2 分别存放在字符数组 S 饥 M1]与 S2[M2]中(LEN(S1)≤M1, LEN(S2)≤M2),并以,@,为串的结束标志。试写一算法,求在 S1 中第一次出现而在 S2 中不出现的字 符的位置。 4.8 已知字符串的存储结构同 4.7 题,并且有 LEN(S1)=M,LEN(S2)=N,试写一算法,从 S1 中位置 k 开始插入字符串 S2,并且取代 S1 中从第 k 个字符开始的连续 t 个字符。设 k+1<M. 4.9 已知字符串存放于字符数组 S[M]中,并以’@’为串的结束标志。试写一算法,判断该字符串是 否是回文(即正读与反读相同)。若字符串是回文,算法返回 1,否则返回 0。 4.10 根据你所确定的一种存储结构设计一个算法,该算法的功能是求串 S 中出现的第一个最长重复 子串的位置与长度。 4.11 已知字符串采用链式存储结构,链结点大小为 1。对于给定的字符串 S1 与 S2,请写一算法,求 在 S1 中第一次出现,而在 S2 中不出现的所有字符。

第四章

各种考试试题
数组部分

选择题 (1)数组是一种线性表结构。 ( ) (2)数组最基本的操作是插入和删除。 ( ) (3)对数组的操作是基于数组下标进行的。 ( ) (4)具有特殊用途的矩阵称为特殊矩阵。 ( ) (5)只需存储 n 阶对称矩阵的下三角部分的元素。 ( ) (6)在 n 阶三对角矩阵中,矩阵的每一列都有 3 个非零元素。 ( ) (7)稀疏矩阵的特点就是矩阵中的元素较少。 ( ) (8)采用三元组表方法存储稀疏矩阵的优点之一是可以随机地访问矩阵中的每一个非零元 素。 ( ) (9)用一维数组存储特殊矩阵的目的是为了节省存储空间。 ( ) (10)从理论上说,任何一个矩阵都可以采用三元组表方法进行存储。 ( ) 填空题。 (1)一般情况下,数组最基本的操作是——。 (2)一个 m 行 n 列的矩阵可以看成是长度为——的线性表,表中的每一个元素是长度为 m 的线性表。 (3)一个 m 行 n 列的矩阵可以看成是长度为——的线性表,表中的每一个元素是长度为 n 的线性表。 (4)已知二维数组 A(4)[6]采用行序为主序方式存储,每个元素占用 4 个存储单元,该数组一 共占用了——个存储单元。 (5)已知二维数组 A[4 爪 6]采用行序为主序方式存储,每个元素占用 3 个存储单元,并且 A10 爪 0]的存储地址为 1200,元素 A12)14]的存储地址是——。 (6)已知二维数组 A14 爪 6]采用列序为主序方式存储,每个元素占用 4 个存储单元, 并且 A[3][4]的存储地址为 1234,元素 A[0][0]的存储地址是——。 (7)对特殊矩阵采用压缩存储方法的目的是——。 (8)一个 20 阶五对角矩阵一共有——个元素,其中有——个非零元素。 (9)将 n 阶三对角矩阵 A 中所有非零元素按照行序为主序方式依次存放于数组 B 中,非零元素 A[i][j] 在 B 中的位置是——。 3.3 单项选择题。
第 28 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

(1)所谓稀疏矩阵是指——的矩阵。 A.零元素较多且分布无规律 ·B 非零元素较少 C.元素较少 D.不适合采用二维数组表示 (2)下面的说法中,不正确的是——。 A.只需存放对称矩阵中包括主对角线元素在内的下(或上)三角部分的元素即可 B‘只需存放对角矩阵中的非零元素即可 C.稀疏矩阵中值为零的元素较多,因此可以采用三元组表方法存储 D.稀疏矩阵中大量值为零的元素分布有规律,因此可以采用三元组表方法存储 (3)与三元组表方法相比,稀疏矩阵采用十字链表表示的优点在于——。 A.便于实现增加或减少矩阵中非零元素的操作 B.便于实现增加或减少矩阵元素的操作 C.节省存储空间 D.可以更快地查找到某个矩阵元素 (4)对稀疏矩阵采用压缩存储,其缺点之一是——。 A.无法判断矩阵的行数和列数 B.无法根据行列号计算矩阵元素的存储地址 C.无法根据行列号查找某个矩阵元素 D.使得矩阵元素之间的逻辑关系更加复杂 (5)将一个 20 阶的五对角矩阵中所有非零元素压缩存储到一个一维数组中,该一维数组至少应该有— —个数组元素。 A.90 B.92 C.94 D.96 (6)将 10 阶三对角矩阵中的所有非零元素按照行序为主序方式依次存放于一维数组中,矩阵的第 7 行 第 8 列的元素在该一维数组中————。 A.是第 22 个数组元素 B.是第 21 个数组元素 C.是第 20 个数组元素 D.不存在 (7)将 10 阶三对角矩阵中的所有非零元素按照行序为主序方式依次存放于一维数组中,一维数组中的 第 18 个数组元素是矩阵——的那个元素。 A.第 6 行第 3 列 B.第 6 行第 7 列 C。第 7 行第 7 列、 D.第 7 行第 6 列 (8)若将 n 阶对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放 在一个一维数组 B 中,则该对称矩阵在 B 中占用了一个数组元素。 A.n2 B.n*(n-1) C.n*(n+1)/2 D.n*(n-1)/2 (9)若将 n 阶三对角矩阵 A 按照行序为主序方式将所有非零元素依次存放在一个一维数组 B 中,则该 三对角矩阵在 B 中占用了——个数组元素。 A.n2 B.3n-2 C.3n D.3n+2 (10)若将对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在 一个一维数组 B 中,那么,A 中某元素 Aij(i<j)在 B 中的位置是——。 A.(i*(i—1))/2+j-1 B.(i*(i—1))/2—j—1 C.(j*(j—1))/2 十 i—1 D.(j*(j-1))/2—i—1 (11)对三对角矩阵 A 采用压缩存储的方法将所有非零元素存放于一个一维数组 BC3n—2]中, 某非零元 素 Aij 在 B 中位置是——。 A.2*i+j-2 B.2*i+j+2 C.2*i+j-3 D.2*i+j-1 4.4 已知一元多项式 f(x)=4X(6)—5X(4)十 7X(2)-1,请写出 f(x)的一维数组表示的两种方法。 4.5 按照压缩存储的思想,对于一个具有 t 个非零元素的 mXn 阶稀疏矩阵,若采用三元组表存储方法,t 到达什么程度时这样做才有意义?
第 29 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

4.6 已知稀疏矩阵 A[6][5]如下所示,请分别写出它的三元组表表示与十字链表表示。

4.8 已知稀疏矩阵 A 为 m 行 n 列,请写出将该稀疏矩阵转换为三元组表表示的算法。 4.9 设 A 为一个 n 阶上三角矩阵,若将此三角矩阵的所有非零元素按照列序为主序分配方式存放在数组 B[n*(n+1)/2]中,a11 存放于 B[0]中,请写出此三角矩阵的非零元素 Aij(i≤j)的寻址公式。 4.10 请写算法,该算法将一个 n 阶矩阵 A 主对角线以下的所有元素(不包括主对角线上的元素)按照列序 为主序方式依次存放于一个一维数组 B 中。 4.11 请写算法,该算法将一个 n 阶矩阵 A 主对角线以下的所有元素(包括主对角线上的元素)按照行序为 主序方式依次存放于一个一维数组 B 中。 4.12 已知 n 阶对称矩阵 A 的下三角部分元素按照行序为主序方式依次存放于一个一维数组 B[m]中, 请写 出输出该对称矩阵的算法。 4.13 已知某二维数组 A[n][n]按照行序为主序方式依次为每个数组元素获取值,请写一算法,求该数组两 条对角线上的元素之乘积。 4.14 已知二维数组 A[m][n],请写一算法,求出该数组最外围一圈的元素之和。 已知二维数组 A[n][n],请写一时间复杂度为 O(1)的算法,将该数组按照顺时针方向旋转若稀疏矩阵采用 三元组表表示,请写出求两个具有相同行、列数的稀疏矩阵相加的算法。 4.17 若在 m*n 阶的矩阵 A 中有一元素 Aij 满足条件:Aij 既是第 i 行元素的最小值,同时又是第 j 列元素 的最大值,此时称 Aij 为 A 的鞍点。试写出求矩阵鞍点的算法。若矩阵中不存在鞍点,应给出相应信息。 4.18 编写一个将十字链表表示的矩阵 A 转置的算法,转置的结果仍采用十字链表表示。 4.19 若稀疏矩阵采用十字链表表示, 请设计两个稀疏矩阵进行相乘运算的算法, 即已知 A 矩阵与 B 矩阵, 求矩阵 C=A*B,并且要求 C 也采用十字链表表示。 4.20 试设计一个算法, 将数组 A[n]中的元素循环右移 k 位, 要求只用一个元素大小的附加空间。 4.21 试 设计一个时间复杂度为 O(n)的算法,该算法将数组 A[n]中的元素循环右移 k 位,要求采用尽可能少的附加 空间。 4.22 n 阶三对角矩阵 A 按行序为主序分配方式把所有非零元素存放于数组 B[3n—2]中,Aij 存放于 B[0] 中,请设计一个算法以确定数组 B 中元素~的值(1≤i,j≤n)。 4.23 已知存放整型数据的一维数组 A[n],请写一时间复杂度为 O(n)的算法,该算法将数组调整为左右两 部分,使得左边所有元素均为奇数,右边所有元素均为偶数。 4.24 已知具有 n 个数组元素的一维数组 A,请写一算法,将该数组中所有值为 0 的元素都依次移到数组 的前端 A[i](0≤i≤n-1)。

综合部分
1.执行下列程序段后,串 X 的值为( S=〞abcdefgh〞; T=〞xyzw〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2);
第 30 页 共 63 页



济南铁道职业技术学院

专升本辅导教材

数据结构

strcat (X,Y); A.〞cdefgh〞 C.〞cdefxy〞 B.〞cdxyzw〞 D.〞cdefef〞 ) B.数组的元素必须从左到右顺序排列 D.数组是多维结构,内存是一维结构 ) B.head (tail (head (LS))) D.tail (tail (head (LS))) ) B.索引和修改

2.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为( A.数组的元素处在行和列两个关系中 C.数组的元素之间存在次序关系 A.tail (head (LS)) C.head (tail (LS)) 4.数组通常具有两种基本运算,即( A.创建和删除

3.从广义表 LS=((p, q), r, s)中分解出原子 q 的运算是(

C.读和写 D.排序和查找 5.设有一 5 阶上三角矩阵 A[1..5,1..5] ,现将其上三角中的元素按列优先顺序存放在一堆数组 B[1..15] 中。已知 B[1]的地址为 100,每个元素占用 2 个存储单元,则 A[3,4]的地址为( ) A.116 B.118 C.120 D.122 6.为查找某一特定单词在文本中出现的位置,可应用的串运算是( ) A.插入 B.删除 C.串联接 D.子串定位 7.已知函数 Sub(s,i,j)的功能是返回串 s 中从第 i 个字符起长度为 j 的子串,函数 Scopy(s,t)的功能为复制串 t 到 s。若字符串 S=″SCIENCESTUDY″,则调用函数 Scopy(P,Sub(S,1,7))后得到( ) A.P=″SCIENCE″ B.P=″STUDY″ C.S=″SCIENCE″ D.S=″STUDY″ 8.三维数组 A[4][5][6]按行优先存储方法存储在内存中,若每个元素占 2 个存储单元,且数组中第一个元素 的存储地址为 120,则元素 A[3][4][5]的存储地址为( ) A.356 B.358 C.360 D.362 9.串 S=″I am a worker″的长度是________。

第五章

树 二叉树

补充内容

后序遍历的非递归算法。 在对二叉树进行后序遍历的过程中,当指针 p 指向某一个结点时,不能马上对它进行 访问,而要先遍历它的左子树,因而要将此结点的地址进栈保存。当其左子树遍历完毕之 后,再次搜索到该结点时(该结点的地址通过退栈得到),还不能对它进行访问,还需要遍 历它的右子树,所以,再一次将此结点的地址进栈保存。为了区别同一结点的两次进栈, 引入一个标志变量 nae,有 0 表示该结点暂不访问 1 表示该结点可以访问 标志 flag 的值随同进栈结点的地址一起进栈和出栈。因此,算法中设置两个空间足够的堆栈,其中, STACKlCM]存放进栈结点的地址, STACK2[M]存放相应的标志 n 昭的值, 两个堆栈使用同一栈顶指针 top, top 的初值为—1。 具体算法如下: #defineH 100 /●定义二叉树中结点最大数目。/ voidPOSTOiRDER(BTREET) {

第 31 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

/*T 为二叉树根结点所在链结点的地址。/ BTREESTACKl[H],p=T; intSTACK2[M],flag,top=—1; if(T!=NULL) d0{ while(p!=NULL){ STACK/[++top]=p; /●当前 p 所指结点的地址进栈●/ STACK2[top]= 0; /,标志 0 进栈●/ p=p->lchild; /●将 p 移到其左孩子结点 x/ } p=STACKl[top); flag=STACK2[top--]; if(flag==0){ STACKl[++top]=p; /,当前 p 所指结点的地址进栈。/ STACK2[toP]=1; /●标志 1 进栈●/ p=p->rchild; /x 将 p 移到其右孩子结点 o/ } else{ VISIT(p); /x 访问当前 p 所指的结点 x/ p=NULL; } }while(p!=NULLtttop!=-1); } 不难分析,上述算法的时间复杂度同样为 O(n) 5.6.3 二叉树的线索化算法 对--X 树的线索化,就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某 种遍历序列中的直接前驱或直接后继的过程,因此,二叉树的线索化过程只能在对二叉树的遍历过程中进 行。 · 下面给出二叉树的中序线索化的递归算法。算法中设有指针 pre,用来指向中序遍历过程中当前访问 的结点的直接前驱结点,pre 的初值为头结点的指针;T 初始时指向头结点,但在算法执行过程中,T 总是 指向当前访问的结点。 voldINTHREAD(TBTREET) { TBTREE pre; if(T!=Null){ INTHREAD(T—>lchild); if(T—>rchild==NULL) T—>rbit=0; if(T—>lchild==NUll); T—>lchild=pre; T—>lbit=0; } if(pre—>rbitc==0) pre—>rchild=T; pre=T; inthread(T->rchild);
第 32 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

}} 平均查找长度(AverageSearchLength):确定一个元素在树中的位置所需要进行的比较次数的期望值。 二叉树的内路径长度(InternalPathLength): 从二叉树根结点到某结点所经过的分支数目定义为该结点的 路径长度。 二叉树中所有结点的路径长度之和定义为该二叉树的内路径长度 IPL。图 7。25(h)给出的二叉排序树 的内路径长度为 IPL:1X2+2X2+3X1+4X2=17 二叉树的外路径长度(ExternalPathLength):为了分析查找失败时的查找长度,在二叉树中出现空子树 时, 增加新的空叶结点来代表这些空子树, 从而得到一棵扩充后的二叉树。 为了与扩充前的二叉树相区别, 这些新增添的空的叶结点用小方块代表,称之为外部结点,树中原有的结点为内部结点。 下图给出了一棵扩充后的二叉树,其外路径长度 EPL 是二叉树中所有外部结点的路径长度之和,即 EPL=2X2+3X1+4X4+5X3 十 6X2=50





5.1 判断题(在你认为正确的题后的括号中打√,否则打 X)。 (1)在树型结构中,每一个结点最多只有一个前驱结点,但可以有多个后继结点。 ( ) (2)在树型结构中,每—个结点不能没有前驱结点。 ( ) (3)在度为 k 的树中,至少有一个度为 k 的结点。 ( ) (4)在度为 k 的树中,每个结点最多有 k—1 个兄弟结点。 ( ) (5)度为 2 的树是二叉树。 ( ) (6)二叉树的度一定为 2。 ( ) (7)在非空完全二叉树中,只有最下面一层的结点为叶结点。 ( ) (8)在完全-y.树中,没有左孩子的结点一定是叶结点。 ( ) (9)在完全二叉树中,没有右孩子的结点一定是叶结点。 ( ) (10)在结点数目一定的前提下,各种形态的二叉树中,完全二叉树具有最小深度。 ( ) (11)满二叉树 一定是完全二叉树。 ( ) (12)满二叉树中的每个结点的度不是 0 就是 2。 ( ) (13)在所有深度相同的二叉树中,满二叉树具有最大结点数目。 ( ) (14)具有 n 个结点的非空二叉树一定有 n—1 个分支。 ( ) (15)n 个结点的二叉树采用二叉链表结构,链表中有 n—1 个存放 NULL 的指针域。 ( ) (16)“退化二叉树”不宜采用顺序存储结构的主要原因是空间浪费较大。 ( ) (17)由二叉树的前序序列和中序序列可以惟一地确定一棵二叉树。 ( )
第 33 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

(18)由二叉树的中序序列和后序序列可以惟一地确定一棵二叉树。 ( ) (19)由二叉树的前序序列和后序序列可以惟一地确定一棵二叉树。 ( ) (20)实现二叉树的按层次遍历算法时需要用到队列结构。 ( ) (21)实现二叉树的遍历算法时不需要用到堆栈结构。 ( ) (22)线索二叉树对应的二叉链表中不存在空的指针域。 ( ) (23)二叉排序树中的任何一棵子树也是二叉排序树。 ( ) (24)一个序列对应的二叉排序树是惟一的。 ( ) (25)按照“逐点插入法”建立的二叉排序树的深度与结点的插入顺序无关。 ( ) (26)在二叉排序树中进行查找的效率与二叉排序树的深度有关。 ( ) (27)在二叉排序树中查找一个结点,查找长度不会超过二叉树的深度。 ( ) (28)给定一组权值,构造出来的哈夫曼树是惟一的。 ( ) (29)哈夫曼树中不存在度为 1 的结点。 ( ) (30)在哈夫曼树中,权值相同的叶结点都在同一层上。 ( ) 5.2 单项选择题。 (1)树型结构最适合用来描述——。 A.有序的数据元素 B.无序的数据元素 C.数据元素之间具有层次关系的数据 D.数据元素之间没有关系的数据 (2)对于一棵具有 n 个结点、度为 4 的树而言,——。 A.树的深度最多是 n-4 B.树的深度最多是 n-3 C.第 i 层上最多有 4x(i-1)个结点 D.最少在某一层上正好有 4 个结点 (3)“二叉树为空”意味着二叉树————。 A.由一些未赋值的空结点组成 B.根结点无子树 巳不存在 D.没有结点 (4)按照二叉树的定义,具有 3 个结点的二叉树有——种形态(不考虑数据信息的组合情况)。 A.2 B.3 C.4 D.5 (5)若一棵度为 7 的树有 8 个度为 1 的结点,有 7 个度为 2 的结点,有 6 个度为 3 的结点,有 5 个度为 4 的结点,有 4 个度为 5 的结点,有 3 个度为 6 的结点,有 2 个度为 7 的结点,则该树一共有——个叶结 点。 A.35 B.28 C.77 D.78 (6)若一棵二叉树有 10 个度为 2 的结点,则该二叉树的叶结点的个数是——。 A.9 B.11 C.12 D.不确定 (7)若一棵满二叉树有 2047 个结点,则该二叉树中叶结点的个数为——。 A.512 B.1024 C.2048 D.4096 (8)深度为 h 的满二叉树的第 i 层有——个结点。(i≤h) A.2(i)—1 B.2(i)-1 C.2(h)—1 D.2(h)-1 (9)深度为 h 的完全二叉树的第 i 层有——个结点。(i<h) A.2(i-1) B.2(i)-1 C.2(h-1) D.2(h)-1 (10)具有 n 个结点的非空完全二叉树的深度为——。 A.n-1 B.n C.Llog2(n)』 D.Llog2(n)』+1 (11)具有 2000 个结点的非空二叉树的最小深度为——。 A.9 B.10 C.11 D.12 (12)若某完全二叉树的深度为 h,则该完全二叉树中至少有——个结点。 A.2(h) B.2(h)-1 c.2(h)+1 D.2(h—1) (13)若二叉树的前序序列与后序序列的次序正好相反,则该二叉树一定是——的二叉
第 34 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

树。 A.空或仅有一个结点 B.其分支结点无左子树 C.其分支结点无右子树 D.其分支结点的度都为 1 (14)任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置——————。 A.都会发生改变 B.不会发生改变 C.有可能会发生改变 D.部分会发生改变 (15)对于一个数据元素序列,按照逐点插入方法建立一棵二叉排序树,该二叉排序树的形状取决于— —。 A.该序列的存储结构 B.序列中数据元素的取值范围 C,数据元素的输人次序 D.使用的计算机的软、硬件条件 (16)对一棵二叉排序树进行——遍历,可以得到该二叉树的所有结点按值从小到大排列 的序列。 A.前序 B.中序 C.后序 D.按层次 (17)除了前序遍历(DLR)、 中序遍历(LDR)与后序遍历(LRD)外, 二叉树的遍历方法还可以有 DRL、 RDL 和 RLD 三种。对于一棵二叉排序树,采用——遍历方法可以得到该二叉排序树的所有结点按值从大到小 排列的序列。 · A.LDR B.LRD C.RLD D.RDL (18)在二叉排序树中进行查找的效率与——有关。 A。二叉排序树的深度 B.二叉排序树的结点的个数 C.被查找结点的度 D.二叉排序树的存储结构 (19)在具有 n 个结点的二叉排序树中查找一个结点的过程的时间复杂度约为——。 A.O(1) B.O(n) C.O(nz) D.O(10gan) (20)下列名词术语中,与数据的存储结构有关系的仅是——。 A.完全二叉树 B.满二叉树 C.线索二叉树 D.二叉排序树 (21)平衡二叉树中任意结点的平衡因子只能是——之一。 A.0,1,2 B.0,1 C.-1,+1 D.0,-1,+1 7. 3 填空题。 (1)任何非空树中有且仅有一个结点没有前驱结点,该结点就是树的——。 (2)树的层次定义为——。 (3)度为 k 的树中第 i 层最多有——个结点(i≥1)。 (4)深度为 h 的 k 叉树最多有——个结点。 (5)非空二叉树一共有——种基本形态。 (6)非空二叉树中第 i 层最多有——个结点。 (7)深度为 h 的二叉树最多有————个结点。 (8)具有 n 个结点的完全二叉树的深度 h 二——。 (9)若二叉树有 N0 个叶结点,n2 个度为 2 的结点,则 N0 与 n2 的关系是——。 (10)若具有 n 个结点的非空 zX.树有 N0 个叶结点,则该二叉树有——个度为 2 的结点,——个度为 1 的结点。 (11)对具有 n 个结点的完全二叉树按照层次从上到下,每一层从左到右的次序对所有结点进行编号, 编号为 i 的结点的双亲结点的编号为——,左孩子的编号为——,右孩子的编号为——。 (12)若具有 n 个结点的二叉树采用二叉链表存储结构,则该链表中有——个指针域,其中有——个指 针域用于链接孩子结点,l-个指针域空闲存放着 NULL。 (13)二叉树的遍历方式通常有——、——、——和_____四种。 (14)已知二叉树的前序遍历序列为 ABDCEFG,中序遍历序列为 DBCAFEG,其后序遍历序列为——。 (15)已知某完全二叉树采用顺序存储结构,结点的存放次序为 A,B,C,D,E,F,G,H,I,J,该完
第 35 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

全二叉树的后序序列为——。 (16)在某二叉树中, 若结点 A 有左孩子 Y 和右孩子 X, 则在结点的前序序列、 中序序列和后序序列中, 结点——一定在结点——的前面。 (17)利用中序线索二叉树进行中序遍历可以不用设置——结构。 (18)对二叉排序树进行——,可以得到由该二叉树中结点组成的按值有序排列的序列。 (19)采用逐点插入法建立序列(54,28,16,34,73,62,95,60,26,43)的二叉排序树后,查找数据 元素 62 共进行——次元素间的比较。 (20)具有 N0 个叶结点的哈夫曼树共有——个结点。 5.4 若结点 A 有三个兄弟(包括 A 本身),并且 B 是 A 的双亲结点。问结点 B 的度是多少? 5.5 若一棵树有 n1 个度为 1 的结点,n2 个度为 2 的结点??nm 个度为 m 的结点,试问:该树一共 有多少个叶结点(即度为 0 的结点个数 no)?请写出推导过程。 5. 6 一棵深度为 h 的满 m 叉树具有如下性质:第 h 层上的结点都是叶结点,其余各层上每个结点 都有 m 棵非空子树。问: (1)第 k 层有多少个结点?(1≤k≤h) (2)整棵树有多少个结点? (3)若按层次从上到下,每层从左到右的顺序从 1 开始对全部结点编号,编号为 i 的结点的双亲结点的 编号是什么?编号为 i 的结点的第 j 个孩子结点(若存在的话)的编号是什么? 5.7 一棵度为 2 的树与一棵二叉树有什么区别? 5.8 请分别画出具有 3 个结点的树和具有 3 个结点的 二叉树的所有形态。 5.9 请分别列出如图所示的二叉树的所有叶结点与分支结点,并分别指出各结点的度数以及所 在的 层次数。

5.10 若一棵具有 n 个结点的二叉树采用二叉链表存储结构。试问:该二叉链表中共有多少个空指针 域?写出推导过程。 5.11 已知某算术表达式的中缀形式为 A+B*C-D/E,后缀形式为 ABC*+DE/-,请写出其前缀形式(利 用二叉树的遍历序列)。 5.12 已知某二叉树的前序序列为 ABDEGCFHIJ,中序序列为 DBGEAHFIJC,请写出后序序列。 5.13 已知某-'X 树的中序遍历序列为 CBGEAFHD,后序遍历序列为 CGEBHFDA,请画出该二叉树 的前序线索二叉树的二叉链表结构的表示。 5.14 已知按前序遍历二叉树的结果为 ABC。试问,有几种不同的二叉树可以得到这一遍历结果? 5.15 请按照算法,SORTTREE 画出对应于序列{15,20,15,7,9,18,61 的二叉排序树。 5.16 给定一组权值 W={14,15,7,3,20,4},请构造出相应的哈夫曼树,并计算其带权的路径长 度 WPL。 5.17 试证明具有 n2 个叶结点的哈夫曼树的分支总数为 2(N0-1)。 5.18 二叉树的深度采用自然语言形式可以描述为:若二叉树为空,则其深度为 0,否则其深度等于 左子树与右子树的最大深度加 1。若二叉树采用二叉链表存储结构,请写出求该二叉树的深度的递归算法。
第 36 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

5.19 已知二叉树采用二叉链表存储结构,根结点的地址为 T。请写出二叉树前序遍历的非递归算法。 5.20 已知两棵二叉树都采用二叉链表存储结构,根结点的地址分别为 T1 和 T2。请写一算法,判断 两棵二叉树是否相似(即具有相同的形态),并给出相应信息。 5.21 已知两棵二叉树都采用二叉链表存储结构,根结点的地址分别为 T1 和 T2。请写一算法,判断 两棵二叉树是否是相同的二叉树,并给出相应信息。 5.22 已知二叉树采用二叉链表存储结构,根结点的地址为 T。请写一算法,释放该二叉树中所有结点 占用的空间。 5.23 已知二叉树采用二叉链表存储结构,根结点的地址为 T。请写一非递归算法统计出该二叉树共有 多少个度为 1 的结点?要求:算法中用到的堆栈采用链式存储结构。 5.24 已知非空二叉树采用二叉链表存储结构,根结点地址为 T。请写出非递归算法,该算法打印数据 信息为 item 的结点的所有祖先结点。假设数据信息为 item 的结点不多于一个。 5.25 已知二叉树采用二叉链表存储结构,根结点的地址为 T。请写一算法,将该二叉链表结构转换为 顺序存储结构。 5.26 已知某具有 n 个结点的二叉树的前序序列与中序序列分别存放于数组 PREOD[n)与 INOD [n]中, 并且各结点的数据值均不相同。试写一非递归算法生成该二叉树的二叉链表结构。 5.27 已知二叉树采用二叉链表存储结构,根结点地址为了。试写一算法,判断该二叉树是否为完全二 叉树,并给出相应信息。 5.28 已知二叉树采用二叉链表存储结构,根结点地址为丁。试写一算法,删去并释放数据值为 key 的 叶结点。 5.29 已知二叉排序树采用二叉链表存储结构,根结点的地址为 T。试写一算法,删去数据值小于或等 于 key 的结点。 5.30 已知二叉树采用二叉链表存储结构,根结点的地址为 T。试写一算法,算法功能是按层次从上到 下,每层从右到左的顺序依次列出二叉树所有结点的数据信息。 5.31 已知二叉树采用二叉链表存储结构,根结点的地址为 T。试写一算法,打印该二叉树所有左子树 的根结点的数据信息。 5.32 已知二叉树采用二叉链表存储结构,根结点的地址为 T。试写一算法,交换二叉树所有左、右子 树的位置,即将结点的左子树变成结点的右子树,右子树变成左子树。 5.33 已知二叉树采用二叉链表存储结构,根结点的地址为丁。请写一算法,输出从根结点到某个指定 结点的路径上各结点的值。 5.34 已知二叉树采用二叉链表存储结构,根结点的地址为 T,请写一算法,判断该二叉树是否是二叉 排序树。 5.35 将图 7.43 所示的树林转换为一棵二叉树。 5.36 分别写出如图 7.44 所示的树的前序遍历序列与后序遍历序列。

5.37 已知某树林转化为二叉树后所对应的顺序存储结构为请画出该树林。
第 37 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

历年考题
1.在具有 n 个叶子结点的严格二叉树中,结点总数为( A.2n+1 B.2n C.2n-1 D.2n-2 ) 2.除根结点外,树上每个结点( B.可有任意多个孩子、一个双亲 C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲 3. 具有 100 个结点的二叉树中, 若用二叉链表存储, 其指针域部分用来指向结点的左、 右孩子, ( 其余 个指针域为空。 A.50 B.99 C.100 D.101 ) 4.若构造一棵具有 n 个结点的二叉排序树,最坏的情况下其深度不会超过( ) )

A.可有任意多个孩子、任意多个双亲

A.n/2 B.n C.(n+1)/2 D.n+1 6.一棵有 16 结点的完全二叉树,对它按层编号,则对编号为 7 的结点 X,它的双亲结点及右孩子结点的 编号分别为( ) A.2,14 B.2,15 C.3,14 D.3,15 7.下列陈述中正确的是( ) A.二叉树是度为 2 的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为 2 的结点 D.二叉树中最多只有两棵子树,并且有左右之分 9、前序遍历序列与中序遍历序列相同的二叉树为 (1) ,前序遍历序列与后序遍历序列相同的二叉树为 (2) 。 (1) A、根结点无左子树的二叉树 B、根结点无右子树的二叉树 C、只有根结点的二叉树或非叶子结点只有左子树的二叉树 D、只有根结点的二叉树或非叶子结点只有右子树的二叉树 (2) A、非叶子结点只有左子树的二叉树 B、只有根结点的二叉树 C、根结点无右子树的二叉树 D、非叶子结点只有右子树的二叉树 10、 假设一棵二叉树的后序遍历序列为 DGJHEBIFCA,中序遍历序列为 DBGEHJACIF,则其前序遍历 序列为 (10) 。 (10) A、ABCDEFGHIJ B、ABDEGHJCFI C、ABDEGHJFIC D、ABDEGJHCFI 11、 设某种二叉树有如下特点;结点的子树数目不是 2 个,则是 0 个。这样的一棵二叉树中有 m(m>O) 个子树为 0 的结点时,该二叉树上的结点总数为 (34) 。 (34) A.2m+l B.2m-1 C.2(m—1) D.2(m+1) 14、二叉树_A_。在完全的二叉树中,若一个结点没有_B_,则它必定是叶结点。每棵树都能唯一地转 换成与它对应的二叉树。由树转换成的二叉树里,一个结点N的左子女是N在原树里对应结点的_C_,而N 的右子女是它在原树里对应结点的_D_。二叉排序树的平均检索长度为_E_。
第 38 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

供选择的答案: A:①是特殊的树 ③是两棵树的总称 B:①左子结点 ③左子结点或者没有右子结点 C~D: ①最左子结点 ③最邻近的右兄弟 ⑤最左的兄弟 E:①O(n) ②o(n)

②不是树的特殊形式 ④是只有二个根结点的树形结构 ②右子结点 ④兄弟 ②最右子结点 ④最邻近的左兄弟 ⑥最右的兄弟 ③O(log2n) ④o(log2n)

15、每一棵树都能唯一地转换为它所对应的二叉树,树的这种二叉树表示对树的运算带来很大的好处。遍 历(周游)是树形结构的一种重要运算,二叉树的基本组成部分是:根(N) 、左子树(L)和右子树(R) 。 因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按___A___次序) ,后序法(即按___B___次 序)和中序法(也称对称序法,即按___C___次序) 。这三种方法相互这间有关联。若已知一棵二叉树的前 序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是___D___,而且可得该二叉树所表示的树的先 根次序序列是___B___。 供选择的答案 A~C:① R L N ② R N L ③ L R N ④ L N R ⑤ N L R ⑥ N R L D、E:① E F G H B C D ② F E G H D C B ③ B C D E F G H ④ E F B G C H D ⑤ B E F C G D H ⑥ F E G B H D C 17.若一棵满三叉树中含有 121 个结点,则该树的深度为________________。 18.设有 k 个结点,在用哈夫曼算法构造哈夫曼树的过程中,若第 i 次合并时已找到权最小的结点 x 和权 次小的结点 y,用 T[x].wt 表示结点 x 的权值,已知 T[x].wt=m, 树后给新根结点的权值赋值的语句为_____________。 19.在下列树中,结点 H 的祖先为_____________。 T[y].wt=n,则合并成新的二叉

20.设一棵二叉树中度为 2 的结点数为 10,则该树的叶子数为________________。 21.如图所示的二叉树,若按后根遍历,则其输出序列为________________。

22.在 n 个结点的线索二叉链表中,有________个线索指针。 23、一棵具有 n 个结点的理想平衡二叉树(即除离根最远的最底层外其他各层都是满的,最底层有若干结 点)有多少层?若设根结点在第 0 层,则树的高度 h 如何用 n 来表示(注意 n 可能为 0)?
第 39 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

24.画出下列二叉树的二叉链表表示图。 分) (6

25.已知树 T 的先序遍历序列为 ABCDEFGHJKL,后序遍历序列为 CBEFDJIKLHGA。请画出树 T。 27.已知树如右图所示, (1)写出该树的后序序列; (2)画出由该树转换得到的二叉树。

28.分别写出下列二叉树的先根、中根、后根遍历序列。 分) (6

第六章



迪杰斯特拉算法如下: SHORTEST—PATH(intcost[][n],intv,intn,intdist[],intpath[)) { ihti,N,u,count,pos[n]; for(i=0;i<n;i++){ s[i]=0; /x 标记数组置 0 x/ dist[i]=cost[V][i]; /。将邻接矩阵第 v 行元素依次送 dist 数组 x path[i][0]=v; /x 源点 v 到各顶点的路径置初值。/ pos[i]=0; /。第 i 条路径的位置计数器置初值 x/ } /x 对辅助数组进行初始化。/ s[v]=l; count=1; /x 计数器赋初值 1 x/ while(count<n){ /‘以下过程执行 n-1 次 x/

第 40 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

u=MINDIST(s,dist); /x 利用 s 和 dist 在尚未找到最短路径的顶点中确定一个与 v 最近的顶点 u。/ s[u]=1; /‘置 u 的标记为 1●/ path[u)C++pos[u]]=u; /x 将 u 添加到 v 到 u 的最短路径中。/ count++; /,计数器累力 n1 x/ while(1){ /。根据 u 更新 v 到所有尚未确定最短路径的顶点的路径长度。/ if((w=SEARCH_VER(s,dist,u))==-1) /,找到通过 u 可以直接到达、且尚未确定最短路径的一个顶点。/ break; /x 未找到,路径长度更新过程结束。/ else{ if(dist[u]+cost[u][w]<dist[w]]{ dist[N]=dist[u]+cost[u][w]; /x 更新路径长度●/ for[i=0;i<pos[u];i++) path[w][i]=path[u][i]; /。用源点 v 到顶点 u 的路径替换源点 v 到 w 的路径。/ } } } .





6.1 判断题(在你认为正确的题后的括号中打√,否则打 X)。 (1)没有顶点的图称为空图。 ( ) (2)图的度是图中所有顶点的度的最大值。 ( ) (3)边上带权值的图称为网(络)。 ( ) (4)图中一个顶点的度应该是它的出度与人度之和。 ( ) (5)n 个顶点的无向图最多有 n(n-1)条边。 ( ) (6)在有向图中,所有顶点的人度之和等于所有顶点的出度之和。 ( ) (7)在无向图中,若顶点 i 到顶点 j 有路径,则这两个顶点之间是连通的。 ( ) (8)在有向图中,若顶点 i 到顶点 j 有路径,则这两个顶点之间是连通的。 ( ) (9)连通图的最小生成树是惟一的。 ( ) (10)邻接矩阵主要用来表示顶点之间的关系。 ( ) (u)若表示某图的邻接矩阵不是对称矩阵,则该图一定是有向图。 ( ) (12)若表示某图的邻接矩阵中出现了全零行或者全零列,则该图一定是非连通图或者非强连通图。 ( ) (13)对于同一个有向图,邻接表中的边结点数目与逆邻接表中边结点数目相等。 ( ) (14)无向图的邻接表中边结点数目一定为偶数。 ( ) (15)邻接表中边结点数目为奇数的图一定是有向图。 ( ) (16)邻接表中边结点数目为偶数的图一定是无向图。 ( ) (17)对图进行广度优先搜索的过程中要用到队列。 ( ) (18)对图进行深度优先搜索的过程中要用到堆栈。 ( ) (19)带权连通图的最小生成树是惟一的。 ( ) (20)最短路径一定是简单路径。 ( ) (21)求源点到各点的最短路径的迪杰斯特拉算法不适用于存在回路的有向网络。 ( ) (22)不能对强连通图进行拓扑排序。 ( )
第 41 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

(23)若 AOV 网中存在拓扑序列,则一般情况下,拓扑序列不是惟一的。 ( ) (24)关键路径是由权值最大的边构成的。 ( ) (25)给定的 AOE 网的关键路径一定是惟一的。 ( ) 6.2 单项选择题。 (1)在一个图中,所有顶点的度数之和等于所有边数的——倍。 A.1/2 B.1 C.2 D.4 (2)一个具有 n 个顶点的无向图最多有——条边。 A.n(n-1)/2 B.n(n-1) C.n(n+1)/2 D.n(2) (3)一个具有 n 个顶点的有向图最多有——条边。 A.n(n-1)/2 B.n(n-1) C.n(n+1)/2 D.n(2) (4)在一个具有 n 个顶点的无向图中,要连通全部顶点至少需要——条边。 A.n B.n+1 C.n-1 D.2n (5)具有 n 个顶点的连通图的生成树一定有——条边。 A.n B.n+1 C.n-1 D.2n (6)若一个非连通的无向图最多有 28 条边,则该无向图至少有——个顶点。 , A.6 B.7 C.8 D.9 (7)在带权图中,两个顶点之间的路径长度是——。 A.路径上的顶点数目 B.路径上的边的数目 C.路径上顶点和边的数目 D.路径上所有边上的权值之和 (8)若具有 n 个顶点的无向图采用邻接矩阵存储方法,该邻接矩阵一定为一个——。 A.一般矩阵 B.对称矩阵 C.对角矩阵 D.稀疏矩阵 (9)若图的邻接矩阵中主对角线上的元素均为 0,其余元素全为 1,则可以断定该图一定 _____. A.是无向图 B.是有向图 C.是完全图 D.不是带权图 (10)有向图的邻接表的第 i 个链表中的边结点数目是第 i 个顶点的——。 A.度数 B.出度 C.人数 D.边数 (11)若某图的邻接表中的边结点数目为奇数,则该图——。 A.一定有奇数个顶点 B.一定有偶数个顶点 C.一定是有向图 D。可能是无向图 (12)若某图的邻接表中的边结点数目为偶数,则该图——。 A.一定是无向图 B。可能是有向图 C.可能是无向图,也可能是有向图 D.一定有偶数个顶点 (13)若无向图有 k 条边,则相应的邻接表中就有——个边结点。 A.k-1 B.k C.2k D.K(2) (14)若有向图有 k 条边,则相应的邻接表中就有——个边结点。 A.k-1 B.k C.2k D.K(2) (15)对于一个不带权的无向图的邻接矩阵而言,——。 A.矩阵中非零元素的数目等于图中边的数目 B.矩阵中非全零的行的数目等于图中顶点的数目 巴第 i 行的非零元素的数目与第 i 列的非零元素的数目相等 D。第 i 行与第 i 列的非零元素的总数等于第 i 个顶点的度数 (16)导致图的遍历序列不惟一的因素有——。 A.出发点不同、遍历方法不同 B,出发点不同、存储结构不同
第 42 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

C,遍历方法不同、存储结构不同 D.出发点不同、存储结构不同、遍历方法不同 (17)若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点,则 该图一定是一个——图。 A.非连通 B.连通 C.强连通 D.完全 (18)可以进行拓扑排序的图一定是——。 A.连通图 B.带权连通图 C.无回路的图 D.无回路的有向图 (19)已知某有向图 G=(V,E),其中 V={v1,v2,v3,v4,v5,v6},E={{v1,v2),(v1,v4),{v2,v6), (v3,v1),(v3,v4),(v4,v5),{v5,v2),{v5,v6)},G 的拓扑序列是—— A.v3,v1,v4,v5,v2,v6 B.v3,v4,v1,v5,v2,v6 C.v1,v3,v4,v5,v2,v6 D.v1,v4,v3,v5,v2,v6 (20)下面关于 AOE 网的叙述中,不正确的是———。 A.若所有关键活动都提前完成,则整个工程一定能够提前完成 B.即使所有非关键活动都未按时完成,整个工程仍有可能按时完成 C.任何一个关键活动的延期完成,都会导致整个工程的延期完成 D.任何一个关键活动的提前完成,都会导致整个工程的提前完成 6.3 设一有向图为 G=(V,E),其中,V={vl,v2,v3,v4},E={<v2,v1>,<v3,v2>,<v4,v3>,<v4, v2>, <v1,v4>},请画出该有向图。 6.4 已知给定有向图如图 8。26 所示。 (1)分别写出每个顶点的人度与出度; (2)画出相应的邻接矩阵与邻接表; (3)画出强连通分量。 6.5 已知给定无向图如图 6.27 所示。 (1)画出相应邻接矩阵; (2)画出相应邻接表。

6.6 证明 n 个顶点的无向图的边数达到的最大值为 n(n—1)/2。 6.7 具有 n 个顶点的强连通图至少有多少条边?这样的图的形状有何特点? 6.8 已知一无向图如图 6.28 所示,请写出其邻接表表示,然后根据该邻接表分别写出从顶 v1 出发进行 深度优先搜索与广度优先搜索时得到的顶点序列。 6.9 已知某带权连通无向图采用邻接矩阵存储方法,邻接矩阵以三元组表形式给出,不包括主对角线元 素在内的下三角形部分元素对应的各三元组分别为(2,1,7),(3,1,6),(3,2,8),(4,1, 9),(4,2, 4),(4,3,6),(5,1,oo),(5,2,4),(5,3,oo),(5,4,2)。该连通图的最小生成树的权值之和是多 少? 6.10 试编写一构造无向图邻接表结构的算法,设该无向图 G=(V,E)以 V={v1,v2,?,vn}与 E={(Vi, Vj)|Vi,Vj 属于 V,i≤n,j≤n}作为输入。
第 43 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

8.11 设计一个算法,将一个已知图的邻接矩阵存储形式转换为邻接表的存储形式。 8.12 已知一个具有 n 个顶点的无向图采用邻接表存储方法。试设计一个算法,删除图中一条边(u,v)。 8.13 一个带权连通图的最小生成树是否一定惟一?什么情况下有可能不惟一? 8.14 已知一带权连通图如图 6.29 所示。请首先写出其邻接矩阵,然后再按 Prim 算法求出其所有可能 的最小生成树。

8.15 根据 SHORTEST PATH 算法, 求出给定有向图(如图 6.30 所示)从顶点 v1 到其他各顶点长度递增的最 短路径,并分别写出执行算法过程中各个数组的变化状态。 6.16 源点到图中其他各顶点的所有最短路径构成一棵生成树,该生成树是否为最小生成树?为什么? 6.17 某航空公司在六个城市设有分公司 v1,v2,v3,v4,v5,v6;矩阵 A 中元素 A[i][j]表示 vi 到 vj 的飞机 票价(A[i][j]=+oo 表示 vi 与 vj 之间不直接通航)。请为该航空公司制作一张由 vl 到各分公司去的最便宜的 通航线路图。

6.18 已知一 AOE 网采用邻接矩阵存储方式,其邻接矩阵为一稀疏矩阵,并采用三元组表形式给出(见图 6.31)。 (1)画出该 AOE 网; (2)分别说明各顶点、有向边表示什么,边上权值代表什么。

6.19 设计出一种求 AOE 网关键路径的算法。 6.20 对给定 AOE 网(如图 8.32 所示)。 (1)分别求出各活动的最早开始时间与最晚开始时间; (2)求出所有关键路径;
第 44 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

(3)该工程完成的最短时间是多少?

第六章 图
1.若<vi, vj>是有向图的一条边,则称( A.vi 邻接于 vj C.vi 和 vj 相互邻接 A.最小生成树中 C.广度优先生成树中 3.下列数据组织形式中, ( A.集合 A.顺序存储结构 C.索引存储结构 A.G 肯定不是完全图 4.邻接表是图的一种( ) B.树形结构 )

历年考试题

B.vj 邻接于 vi D.vi 与 vj 不相邻接 ) B.深度优先生成树中 D.深度优先生成森林中 )的各个结点可以任意邻接。 C.线性结构 B.链式存储结构 D.散列存储结构 ) B.G 一定不是连通图 D.图状结构

2.在一个带权连通图 G 中,权值最小的边一定包含在 G 的(

5.如果无向图 G 必须进行二次广度优先搜索才能访问其所有顶点,则下列说法中不正确的是( C.G 中一定有回路 D.G 有 2 个连通分量 6.一个带权的无向连通图的最小生成树( ) A.有一棵或多棵 B.只有一棵 C.一定有多棵 D.可能不存在 7.下列有关图遍历的说法中不正确的是( ) A.连通图的深度优先搜索是一个递归过程 B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C.非连通图不能用深度优先搜索法 D.图的遍历要求每一顶点仅被访问一次 8.n 个顶点的有向完全图中含有向边的数目最多为( ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 9.已知一个有向图如右所示,则从顶点 a 出发进行深度优先偏历,不可能得到的 DFS 序列为( A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b

)

第 45 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

10.顶点数为 n、边数为 n(n-1)/2 的无向图称为_____________。 1.一个具有 n 个顶点的有向完全图的弧数为________________。 12.若以邻接矩阵表示有向图,则邻接矩阵上第 i 行中非零元素的个数即为顶点 vi 的________。 13.若采用邻接矩阵结构存储具有 n 个顶点的图,则对该图进行广度优先遍历的算法时间复杂度为 ________。 14、 在用于表示有向图的邻接矩阵中, 对第 i 行的元素进行累加, 可得到第 i 个顶点的( )度, 而对第 j 列的元素进行累加, 可得到第 j 个顶点的( )度。 15、 一个连通图的生成树是该图的( )连通子图。若这个连通图有 n 个顶点, 则它的生成树有( ) 条边。 16、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句,将其编号填入相应的括号内。 (1) 对于一个具有 n 个结点和 e 条边的无向图,若采用邻接表表示,则顶点表的大小为( A ) ,所有边 链表中边结点的总数为( B ) 。 (2) 采用邻接表存储的图的深度优先遍历算法类似于树的( C ) 。 (3) 采用邻接表存储的图的广度优先遍历算法类似于树的( D ) 。 (4) 判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用( E ) 。 供选择的答案 A:① n ② n+1 ③ n-1 ④ n+e B:① e/2 ② e ③ 2e ④ n+e C~D:① 中根遍历 ② 先根遍历 ③ 后根遍历 ④ 按层次遍历 E:① 求关键路径的方法 ② 求最短路径的 Dijkstra 方法 ③ 深度优先遍历算法 ④ 广度优先遍历算法 17.已知无向图 G 的邻接表如下,请写出其从顶点 V2 开始的深度优先搜索的序列。 分) (4

18.下列函数 MDFSForest 的功能是,对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历,输出 所得深度优先生成森林中各条边。请在空缺处填入合适内容,使其成为一个完整的算法。 #define MaxMun 20 //图的最大顶点数 typedef struct { char vexs [MaxNum]; //字符类型的顶点表 int edges [MaxNum][MaxNum]; //邻接矩阵 int n, e; //图的顶点数和边数 }MGraph; //图的邻接矩阵结构描述 typedef enum {FALSE, TRUE} Boolean; Boolean visited [MaxNum]; void MDFSTree (MGraph *G, int i); void MDFSForest (MGraph *G)
第 46 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

{ int i, k; for (i=0; i <G -> n; i++) visited [i] = for (k = 0; k<G -> n; k++) if (!visited [k]) MDFSTree (G,k); } void MDFSTree (MGraph *G, int i) { int j; visited [i]=TRUE; for (j=0; j<G -> n; j++) { if ( { printf (〃<%c, %c>〃G -> vexs [i], G -> vexs [j]); (3) } } } 19.已知无向图 G 的邻接矩阵如下,假设对其每行元素访问时必须从右到左,请写出从 V0 开始的深度优 先搜索的序列。 分) (4
V0 ? V1 ? ? V2 ? ? V3 ? V4 ? ? 0 1 1 0 0 ? 1 0 1 1 1 ? ? 1 1 0 1 1 ? ? 0 1 1 0 1 ? 0 1 1 1 0 ? ?
v0 v1 v2 v3 v4

(1)

;

(2)

)

;

21、下列算法是根据一个带权图的邻接矩阵存储结构 G1 建立该图的邻接表存储结构 G2,请填入合适的内 容,使其成为一个完整的算法。 void convertM(MGraph *G1,ALGraph *G2) { int i,j; EdgeNode * p; G2->n=G1->n; G2->e=G1->e; for(i=0;i<G1->n;i++) { G2->adjlist[i].vertex=G1->vexs[i]; G2->adjlist[i].firstedge= (1) ; } for (i=0;i<G1->n;i++) for (j=0;j<G1->n;j++)
第 47 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

if(G1->edges[i][j]<INFINITY) { p=(EdgeNode *) malloc(sizeof(EdgeNode)); p->weight= (2) ; p->adjvex=j; p->next=G2->adjlist[i].firstedge; (3) ; } } 22、写出求连通网络的最小生成树的 Prim 算法的实现。 23、写出求连通网络的最小生成树的克鲁斯卡尔算法的实现。

第七章


查找


7.1 判断题(在你认为正确的题后的括号中打√,否则打 X)。 (1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。 ( ) (2)查找成功与否的关键在于是否按主关键字查找。 ( ) (3)顺序文件必须用一片地址连续的存储空间来存放。 ( ) (4)只有在顺序存储结构上才能采用顺序查找方法。 ( ) (7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。 ( ) (8)建立稠密索引的优点是节省存储空间。 ( ) (9)分块查找的效率与文件中的记录被分成多少块有关。 ( ) (10)分块查找过程是首先查找索引表,然后再到相应的块中具体查找记录。 ( ) (11)B-树和 B 十树都是用来实现动态索引的。 ( ) (12)在 B-树上可以进行顺序查找。 ( 1 (13)在 B+树上可以进行顺序查找。 / 1 (14)采用散列方法存储线性表,不能存储数据元素之间的关系。 ( ) (15)在散列文件中进行查找不涉及关键字的比较。 ( ) (16)散列冲突是指同一个关键字对应了多个不同的散列地址。 ( ) (17)散列表的负载因子等于存人散列表中的关键字的个数。 ( ) (18)在散列表的查找过程中,关键字的比较次数与表中关键字的数目直接相关。 ( ) (19)在利用线性探测法处理冲突的散列表中,散列函数值相同的关键字总是存放在一片地址连续的存 储单元中。 (20)在采用链地址法处理冲突的散列表中,散列函数值相同的关键字是链接在同一个链表中的。 ( ) 7.2 单项选择题。 (1)衡量查找算法性能好坏的主要标准是 。 A.参加比较的关键字值的多少 B.被查找的关键字值在关键字序列中的位置 C.关键字序列中是否存在被查找关键字值 D.关键字值的平均比较次数的多少 (2)顺序查找方法的优点之一是— 。 · A.对于被查找对象几乎没有限制 B.适合排序连续顺序文件的查找
第 48 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

C.适合链接顺序文件的查找 D.查找时间效率高 (3)对线性表采用折半查找,该线性表必须 。 A.元素按值有序排列 B.采用顺序结构 C.元素按值有序排列,并且采用顺序存储结构 n 元素按值有序排列,并且采用链式存储结构 (4)下面的说法中,不正确的是——。 A.折半查找方法不适用于按值有序链接的链表的查找 B.折半查找方法适用于按值有序的顺序表的查找 C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找 D.折半查找方法适用于排序连续顺序文件的查找 (5)在有序表(k1,k2,?,k9,)中采用折半查找方法查找 99 次,其中,至少有一个元素被比较了 99 次,该元素是——。 A.K99 B.k50 C.K49 D.k1 (6)为了实现分块查找,线性表必须采用——结构。 A.顺序存储 B.链式存储 C.索引存储 D.散列存储 (7)只能在顺序存储结构上才能实现的查找方法是 法。 A.顺序查找 B.树型查找 C.折半查找 D.散列查找 (8)在具有 15 个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录,需要进行 ——次关键字的比较。 A.0 B.4 C.5 D.15 (9)若在 100 个记录中查找其中任意一个记录,最多只要比较 5 次,则所采用的查找方法可能是——。 A.折半查找 B.树型查找 C.分块查找 D.散列查找 (10)若在 n 个记录中查找其中任意一个记录至少要比较 2 次,则所采用的查找方法可能是 A.分块查找 B‘折半查找 C.树型查找 D.散列查找 (11)折半查找过程可以利用一棵称之为判定树的二叉树来描述。 在长度为 12 的序列中进行折半查找对应 的判定树的根结点的右孩子的值(某元素在序列中的位置)是——。 A.7 B.8 C.9 D.10 (12)若在序列中采用折半查找方法进行查找,用来描述该查找过程的判定树的形状与——有关。 A.序列中元素的值 B.序列中元素的排列次序 C.序列中元素的类型 D.序列中元素的个数 (13)在某序列中采用折半查找方法查找某个元素,依次被比较过的元素在该序列中的位置只能是——。 A.10,15,12,18,19 B.10,15,12,13,14 C.10,15,16,18,19 D.10,15,11,13,14 (14)在某序列中采用折半查找方法查找某个元素, 依次被比较过的元素在该序列中的位置不可能是——。 A.10,5,7,8,9 B.10,5,2,1 C.10,5,6,7,8 D.10,5,7,6 (15)将数据元素 2,4,6,8,10,12,14,16,18,20 依次存放于一个一维数组中,然后采用折半查找 方法查找元素 12,被比较过的数组元素的下标依次为——。 A.10,16,12 B.10,12,16 C.4,7,5 D.4,5,7 (16)索引文件中的索引表具有的特点是————。 A.索引项按关键字值有序,并且由用户提供
第 49 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

B.索引项按关键字值有序,并且由系统提供 C.索引项按关键字值无序,并且由用户提供 D.索引项按关键宇值无序,并且由系统提供 (17)m 阶 B-树中的 m 是指——。 A.每个结点至少具有 m 棵子树 B.每个结点最多具有 m 棵子树 C.分支结点中包含的关键字的个数 D.m 阶 B-树的深度 (18)下面关于 B-树和 B+树的叙述中,不正确的是——。 A.B-树和 B+树都是平衡的多分树 B.B-树和 B+树都可以用于文件的索引结构 D.B—树和 B+树都能有效地支持随机检索 (19)下面的命题中,不成立的是 。 A.m 阶 B-树中的每一个分支结点的子树的数量都小于或等于 m。 B.m 阶 B-树中的每一个分支结点的子树的数量都大于或等于 m/2 上取整 C.m 阶 B-树中的任何一个结点的子树的深度都相等。 D.m 阶 B—树中有 k 个子树的分支结点包含 k—1 个关键字。 (20)评价散列函数质量好坏的标准是——。 A.函数是否简单 B.计算是否快 C.是否是解析式 D.函数的取值是否均匀 (21)在一个初始状态为空的散列表中依次插入关键字序列(MON, TUE, WED, THU, FRI, SAT, SUN), 散列函数为 H(key):i%7,其中,i 为关键字 key 的第一个字母在英文字母表中的序号,地址值域为[0:6], 采用线性再散列法处理冲突。 (22)在具有 n 个元素的序列中进行查找,平均查找长度为 O(n)的方法是——。 A.顺序查找方法 B.散列查找方法 C.分块查找方法 D.树型查找方法 7.3 填空题。 (1)文件的逻辑结构是指——,文件的物理结构是指——。 (2)文件在物理结构中通常有——、——和——三种组织方式。 (3)文件的关键字是——。 (4)文件最基本操作是 和 。 (5)对线性表采用折半查找方法,该线性表必须采用——存储结构,并且——。 (6)在按值有序的线性表(5,8,11,12,15,20,32,41,57)中采用折半查找法查找 20 需要进行—— 次元素间的比较。 (7)具有 n 个结点的判定树的深度 h = —— 。 (8)若每个记录的查找概率相等, 则在具有 n 个记录的顺序文件中采用顺序查找法的平均查 找长度 ASL=——。 (9)在具有 n 个记录的排序连续顺序文件中采用折半查找法的平均查找长度 ASL=? (10)索引文件的索引表中的一个索引项是——之间的对照关系。 (11)索引文件包括——和——两个部分。 (12)索引表的特点是——,并且——。 (13)在索引文件中查找一个记录的过程是先查——,然后——。 (14)具有 144 项的表分成——块最好,若每块的最佳长度为 8,则平均查找长度为—— (15)在 3 阶 B-树上,每个分支结点包含的子树的数目最多为——,最少为——。
第 50 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

(16)一棵 B+树上通常有两个头指针(即查找的人口指针),其中一个指向——,另一个指向——。 (17)散列函数建立了——之间的对应关系。 (18)设计一个散列表通常应包括三个内容,分别是——、——和——。 (19)一个好的散列函数是指——。处理冲突的方法通常有——、——和——一 O (20)一个待散列存储的线性表为 K 二(18,25,63,50,42,32,9),散列函数为 H(k):k%9,则与元 素 18 发生冲突的元素有——个。 7.4 试叙述索引顺序文件与顺序文件相比较的优缺点,指出一种适用于索引顺序文件的外存设备。 7.5 已知一个长度为 12 的线性表(Dec,Feb,Nov,Oct,Jul,Sept,Aug,Apr,May,Jun,Jan,Mar)。 (1)按该线性表中元素的顺序构造出一棵二叉排序树; (2)若每个元素的查找概率均等,查找此二叉排序树中任意一个结点的平均查找长度 ASL 是多少? (3)若对线性表的元素按字典顺序从小到大排列以后,再用折半查找方法,则查找其中任意一个元素的 平均查找长度 ASL 是多少? (4)画出相应的平衡二叉树。 7.6 折半查找过程可以利用一棵判定树来描述。请画出 n‘13 时的判定树。 7.7 何谓散列冲突?何谓冲突处理?简要说明冲突处理的过程。 7.8 已知散列函数为 H(k)二 k%7,并采用线性探测再散列方法处理冲突,所建立的散列表如下所示, 请依次将关键字 17,27 填人表中。 7.9 在初始为空的散列表中依次插入以下关键字序列:Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sept, Oct,Nov,Dec。散列函数为 H(k):i%p,其中,i 为关键字的第一个字母在英文字母表中的序号。请分别 画出按以下两种情况构成的散列表: (1)散列地址空间为[0,12],p=13,用线性再散列法处理冲突; (2)散列地址空间为[0,6],p=7,用链地址法处理冲突。 7.10 在散列函数与散列地址范围都分别相同的前提下,采用链地址法处理冲突比采用开放地址法处理 冲突的时间效率要高,为什么? 7.11 已知有长度为 M 的散列表 HT[0,M-1],散列函数为 H(k),并且采用线性探测再散列方法处理冲 突。请写出在该散列表中查找关键字值为 key 的元素存在与否的算法。若存在,则给出它在表中的位置, 否则给出相应的信息。 7.12 请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为 H(k),处理冲突的方法为线 性再散列法。 7.13 请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为 H(k),处理冲突的方法为链 地址法。 7.14 已知一长度为 n 的线性表 A 和待散列地址空间为[0,m—1),其中 m≥n。若采用除留余数法构造 散列函数与步长为根号下 N 下取整的线性探测再散列法处理冲突, 请分别写出建立该散列表和在该散列表 上进行查找的算法。 7.15 已知散列函数为 H(k)=(3*k)%11,采用线性探测再散列法处理冲突。对下列关键字值序列构造一个 散列地址空间为[0,10]的散列表,并求出 ASL。 (22,41,53,8,46,30,1,3l,66)

第七章 历年考试题
11.若用二分查找法取得的中间位置元素键值大于被查找值,说明被查找值位于中间值的前面,下次的查 找区间为从原开始位置至( A.该中间位置 C.该中间位置+1 ) B.该中间位置-1 D.该中间位置/2
第 51 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

12.散列文件不能( A.随机存取 C.按关键字存取 次数为( A.n/2 )

) B.索引存取 D.直接存取

13.若检索顺序文件各个记录的概率相同,设文件占用的页块数为 n,则按关键字存取时的平均访问外存 B.n

C.n/4 D.log n 10.在最坏的情况下,查找成功时二叉排序树的平均查找长度( ) A.小于顺序表的平均查找长度 B.大于顺序表的平均查找长度 C.与顺序表的平均查找长度相同 D.无法与顺序表的平均查找长度比较 11.闭散列表中由于散列到同一个地址而引起的“堆积”现象,是由( ) A.同义词之间发生冲突引起的 B.非同义词之间发生冲突引起的 C.同义词之间或非同义词之间发生冲突引起的 D.散列表“溢出”引起的 12.从外存设备的观点看,存取操作的基本单位是( ) A.逻辑记录 B.数据元素 C.文件 D.物理记录 13.对文件进行检索操作时,每次都要从第一个记录开始的文件是( ) A.顺序文件 B.索引文件 C.顺序索引文件 D.散列文件 5、考虑具有如下性质的二叉树:除叶子结点外,每个结点的值都大于其左子树上的一切结点的值,并 小于等于其右子树上的一切结点的值。 现把9个数1,2,3,?8,9填入下图所示的二叉树的9个结点中,并使之具有上述性质。此时,n1 的值是_A_,n2的值是_B_,n9的值是_C_。现欲把101/2放入此树,并使该树保持前述性质,增加 的一个结点可以放在_D_或_E_。 o n1 / \ o n2 o n3 / \ \ o n4 o n5 o n6 / \ \ o n7 o n8 o n9 供选择的答案 A~C:①1 ②2 ⑦7 ⑧8 D、E:①n7下面 ⑤n1与n2之间 ③3 ④4 ⑨9 ②n8下面 ⑥n2与n4之间 ⑤5 ⑥6 ④n6下面 ⑧n3与n6之间

③n9下面 ⑦n5与n9之间

1、散列法存储的基本思想是根据_A_来决定_B_ , 碰撞 (冲突) 指的是_C_ , _D_越大, 发生碰撞的可能 性也越大。 处理碰撞的两类主要方法是_E_。 供选择的答案 A 、B 、D :①存储地址 ②元素的序号 ③元素个数 ④关键码值 ⑤非码属性 ⑥平均检索长度 ⑦负载因子 ⑧散列表空间 C : ①两个元素具有相同序号
第 52 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

②两个元素的关键码值不同, 而非码属性相同 ③不同关键码值对应到相同的存储地址 ④负载因子过大 ⑤数据元素过多 E : ①线性探查法和双散列函数法 ②建溢出区法和不建溢出区法 ③除余法和折叠法 ④拉链法和开地址法 ●已知一个线性表(38,25,74,63,52,48),采用的散列函数为 H(Key)=Key mod 7,将元素散列到表长 为 7 的哈希表中存储。若采用线性探测的开放定址法解决冲突,则在该散列表上进行等概率成功查找的平 均查找长度为 (11) ;若利用拉链法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为 (12) 。 (11) A、1.5 B、1.7 C、2.0 D、2.3 (12) A、1.0 B、7/6 C、4/3 D、3/2 (试题5 ) 在二叉排序树中,每个结点的关键码值__A__,__B__一棵二叉排序树,即可得到排序序列。同一个结 点集合,可用不同的二叉排序树表示,人们把平均检索长度最短的二叉排序树称作最佳二叉排序树,最佳 二叉排序树在结构上的特点是__C__. 供选择的答案 A:① 比左子树所有结点的关键码值大,比右子树所有结点的关键码值小; ② 比左子树所有结点的关键码值小,比右子树所有结点的关键码值大; ③ 比左右子树的所有结点的关键码值大 ; ④ 与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系。 B:① 前序遍历 ②中序(对称)遍历 ③后序遍历 ④层次遍历 C:① 除最下两层可以不满外,其余都是充满的 ; ② 除最下一层可以不满外,其余都是充满的; ③ 每个结点的左右子树的高度之差的绝对值不大于1 ; ④ 最下层的叶子必须在左边 。 23.动态查找表在开散列表上通常采用_____________来解决冲突问题。 24.对于有 10 个元素的有序表采用二分查找,需要比较 3 次方可找到其对应的键值,则该元素在有序表 中的位置可能是______________。 25.查找表的逻辑结构与线性结构、树型结构等相比,根本区别在于______________。 23.查找表的数据结构有别于线性表、树型结构等,其逻辑结构为________________。 24.长度为 L 的顺序表,采用设置岗哨方式顺序查找,若查找不成功,其查找长度为__________。 25.在开散列表上查找某元素时,通常分两步进行,首先必须计算该键值的散列地址,然后在地址指针所 指________________中查找该结点。 26.文件的检索有顺序存取、________________和按关键字存取三种方式。 25.若要找出所有工资低于 1500 元,职称是副教授,及所有工资低于 2000 元,职称是教授的记录,则查询 条件是________。 29.在关键字序列(07,12,15,18,27,32,41,92)中用二分查找法查找和给定值 92 相等的关键字,请 写出查找过程中依次和给定值“92”比较的关键字。 28.为关键字(17,33,31,40,48)构造一个长度为 7 的散列表,设散列函数为 h(key)=key%7,用开放 定址法解决冲突的探查序列是 hi = (h(key) + i(key%5+1))%7 (1)画出构造所得的散列表; (2)求出在等概率情况下查找成功时的平均查找长度。 0≤i≤6

第 53 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

32.设闭散列表容量为 7(散列地址空间 0..6) ,给定表(30,36,47,52,34) ,散列函数 H(k)=k mod 6,采用线性探测法解决冲突,要求: 分) (7 (1)构造散列表; (2)求查找数 34 需要的比较次数。 32.用二分查找法对一个长度为 10 的有序表进行查找,填写查找每一元素需要的比较次数。 分) (8 元素下标 比较次数 八、设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }, (1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。 若发生不平衡, 指明需做的 平衡旋转的类型及平衡旋转的结果。 (2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。 1 2 3 4 5 6 7 8 9 10

第八章

排序 习题

8.1 单项选择题。 (1)排序方法的时间效率主要用排序过程中——来衡量。 A.排序趟数的多少 B.参加排序的序列中元素的多少 D.排序过程中元素移动或者交换的次数 D.排序过程中元素之间的比较次数 (2)从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放在已排序序列中的合适位置, 这种排序方法称为——。 A.选择排序法 B.插入排序法 C.泡排序法 D.堆积排序法 (3)每一趟排序从未排序序列中挑选一个值最小的元素,然后将其放在已排序序列的右端,这种排序方法 称为——。
第 54 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

A.选择排序法 B.插入排序法 C.快速排序法 , D.谢尔排序法 (4)从未排序序列中任选出一个元素,该元素将当前参加排序的序列分成前后两个部分,前一部分中所有 元素均小于等于所选元素,后一部分中所有元素均大于等于所选元素,而 所选元素处在排序的最终位置,然后分别对被分成的两部分中元素个数超过 1 的部分重 复上述过程,直至排序结束。这种排序方法称为——。 A.选择排序法 B.插入排序法 C.快速排序法 D.二路归并排序法 (5)与直接插入排序方法比较,折半插入排序方法减少了排序过程中的——。 A.排序趟数 D.元素之间的比较次数 C.元素的移动次数 D.辅助空间 (6)在所学过的排序方法中,排序趟数与序列的原始状态有关的方法是——。 A.选择排序法 B.谢尔排序法 C.堆积排序法 D.泡排序法 (7)对序列(49,38,65,97,76,13,47,50)采用折半插入排序法进行排序,当把第七个元素 47 插入到 已排序序列中,为寻找插入的合适位置需要进行——次元素间的比较。 A.3 B.4 C.5 D.6 (8)若对序列(tang,deng,an,wang,shi,bai,fang,1iu)采用选择排序法按字典顺序进行排序,下面给 出的四个序列中,——是第三趟的结果。 A.an,bai,deng,wang,tang,fang,shi,1iu B.an,bai,deng,wang,shi,tang,fang,liu C.an,bai,deng,wang,shi,fang,tang,1lu D.an,bai,deng,wang,shi,1iu,tang,fang (9)对于序列(49,38,65,97,13,27,50)按从小到大进行排序,——是初始步长 d=4 的谢尔排序法第 一趟的结果。 A.49,76,65,13,27,50,97,38 B.3,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 (10)对序列(Q,D,F,X,A,P,N,B,Y,M,C,W)采用二路归并排序,下面的四个序列中——是 第三趟的结果。 A.A,B,D,F,N,P,Q,X,C,W,M,Y B.A,B,F,D,N,P,Q,X,C,M,W,Y C.A,B,D,F,P,Q,X,N,C,M,W,Y D.A,B,D,F,N,P,Q,X,C,M,W,Y (11)对具有 n 个元素的序列采用选择排序法排序,排序趟数为——。 A.n B.n-1 C.n+l D.Llog2n』 (12)对具有 n 个元素的序列采用泡排序法排序,排序趟数为——。 A.n B.n-1 C.[1,n] D.[1,n-1] (13)对具有 n 个元素的序列采用堆积排序法排序,排序趟数为——。 A.n B.Lnlog2nJ C.L10g2nJ D.n-1 (14)根据(大顶)堆积的定义,下面的四个序列中——是一个堆积。 A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20,15
第 55 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

C.75,45,65,30,15,25,20,10 D.75,45,65,10,25,30,20,15 (15)插入排序法的时间花费主要取决于元素间的比较次数,若具有 n 个元素的序列初始时已经是一个 递增序列,则排序过程中一共要进行——次这种比较。 A.n B.n-1 C.n(n-1)/2 D.n2 (16)插入排序法的时间花费主要取决于元素间的比较次数,若具有 n 个元素的序列初始时为一个递减 序列,则排序过程中一共要进行——次元素间的比较。 A.n B.n-1 C.n(n-1)/2 D.n2 (17)若——,则称这样的排序方法为非稳定性排序方法。 A.排序前后,值相同的元素的先后相对位置可能会颠倒 B.排序前后,值相同的元素的先后相对位置一定会颠倒 C.对同一个序列,每次排序的结果可能不相同 D.排序结果不可预测 (18)下面四种排序方法中,——是一种稳定性排序方法。 A.插入排序法 B.选择排序法 C.快速排序法 D.谢尔排序法 (19)下面四种排序方法中,——占用的辅助空间最多。 A.插入排序法 B.堆积排序法 C.快速排序法 D.二路归并排序法 (20)在序列中各元素已经排好序的情况下,采用——方法可以尽可能快地结束排序。 A,插入排序 B.泡排序 C.快速排序 D.堆积排序 (21)在序列中各元素已经排好序的情况下,采用——方法的时间效率最低。 A。插入排序 B.泡排序 C.快速排序 D.堆积排序 (22)在序列中各元素已经排好序的情况下,采用——方法时元素的移动次数最少。 A。选择排序 B.快速排序 C.堆积排序 D.归并排序 (23)若序列的原始状态为 9,8,7,6,5,4,3,2,1,要想获得比较好的时间效率,不应该采用下 列四种排序方法中的——方法。 A。谢尔排序 B.快速排序 C.堆积排序 D.归并排序 (24)若序列的原始状态为 1,2,3,4,5,10,6,7,8,9,要想使得排序过程中元素的比较次数最 少,应该采用——方法。 A,插入排序 B.选择排序 C.谢尔排序 D.泡排序 (25)当参加排序的数据量较大,元素的分布又比较随机,并且无排序稳定性要求,宜选择_____. A。 插入排序法 B. 选择排序法 C. 快速排序法 D. 堆积排序法 10. 请以关键字序列{503, 2 87,512,75,93,170,365,602,612}为例,分别写出执行以下排序算法时每一趟排序的结果,并分别 统计每一趟排序过程中所进行的关键字比较的次数。 (1)插入排序; (2)谢尔排序; (3)堆积排序; (4)二路归并排序。 8.3 什么是堆积?请根据堆积的定义和堆积的构造方法写出对应于序列{12,18,4,36,23,41,20,50, 19}的初始堆积。 8.4 已知序列为{12,2,16,30,8,28,4,10,20,6},请分别写出采用下列排序方法进行排序时每一 趟结束的结果。 (1)选择排序法;
第 56 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

(2)泡排序法; (3)快速排序法; (4)基数排序法。 8.5 设有 10000 个元素组成的无序序列,希望尽快挑选出其中前 10 个(仅挑出前 10 个㈠最大值元素,在不改变已有算法结构的前提下,以下几种内排序算法中哪一种最合适?为什么? (1)选择排序法; (2)快速排序法; (3)堆积排序法; (4)泡排序法。 8.6 请写出快速排序法的非递归算法。 8.7 请写出用带头结点的线性链表作为存储结构时的选择排序算法。设链表中头结点的指针为 list;要求 算法中不得使用除链表以外的其他链结点空间,也不得改变链结点数据域内容。 8.8 请写出用带头结点的双向循环链表作为存储结构时的插入排序算法。设头结点指针为 list;算法中不 得使用除链表外的其他链结点空间,也不得改变链结点数据域内容。 8.9 请回答在你所学过的内排序方法中,哪些方法是稳定的?哪些方法是不稳定的?并为每一 种不稳定的 排序方法举出一个不稳定的实例。 8.10 选择排序法与堆积排序法每一趟排序都是从当前未排好序的元素中选出一个元素,而一般情况下堆 积排序法的时间效率远比选择排序法的时间效率要高,为什么? 8.11 若 n 个值各不同的元素存在于数组 A[n]中,则可按如下所述过程实现的排序方法称为计数排序法: 另设一个数组 B[n](初值均为 0),对 A 中每个元素 A[i],统计 A 中值比它小的元素的个数并存于 B[i]中, 则与 B[i]0 对应的元素 A[i]必为 A 中值最小的元素;然后,根据 B[i]值的大小将 A 中元素重新排列(即根据 BC 门确定 A[i]的排序位置)。请编写一算 法,实现上述排序方法。 8.12 请为下列每种情况选择合适的内排序方法: (1)n=30,且要求最坏情况下速度最快; (2)n=30,且要求既要快,又要排序稳定; (3)n=1000,要求平均情况下速度最快; (4)n=1000,要求最坏情况下速度最快; (5)n=1000,要求既要快,又要最节省存储空间。

第八章

排序

历年考试题


12.当在二叉排序树中插入一个新结点时,若树中不存在与待插入结点的关键字相同的结点,且新结点的 关键字小于根结点的关键字,则新结点将成为( A.左子树的叶子结点 C.右子树的叶子结点 13.希尔排序的增量序列必须是( A.递增的 C.递减的 置,则该排序方法称为( A.插入排序 C.冒泡排序 A.O(log2n) B.左子树的分支结点 D.右子树的分支结点 ) B.随机的 D.非递减的 ) B.归并排序 D.堆排序 ) B.O(n)

14.如果在排序过程中,每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位

2. 设某二维数组 A [1..n, 1..n] 则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为 , (

第 57 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

C.O(nlog2n) A. (15,30,22,93,52,71) C. (15,52,22,93,30,71) 过一趟冒泡排序后的序列为(

D.O(n2) ) B. (15,71,30,22,93,52) D. (93,30,52,22,15,71) )

14.下列关键码序列中,属于堆的是(

15.已知 10 个数据元素为(54,28,16,34,73,62,95,60,26,43) ,对该数列按从小到大排序,经 A.16,28,34,54,73,62,60,26,43,95 B.28,16,34,54,62,73,60,26,43,95 C.28,16,34,54,62,60,73,26,43,95 D.16,28,34,54,62,60,73,26,43,95 14.一组记录的键值为(46,74,18,53,14,20,40,38,86,65) ,利用堆排序的方法建立的初始堆 为( ) A. (14,18,38,46,65,40,20,53,86,74) B. (14,38,18,46,65,20,40, 53,86,74) C. (14,18,20,38,40,46,53,65,74,86) D. (14,86,20,38,40,46,53,65,74,18) 15.对序列(22,86,19,49,12,30,65,35,18)进行一趟排序后得到的结果如下: (18,12,19, 22,49,30,65,35,86) ,则可以认为使用的排序方法是( ) A.选择排序 B.冒泡排序 C.快速排序 D.插入排序 12.在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序方法是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 13.不可能生成右图所示二叉排序树的关键字序列是( ) A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5

14.ALV 树是一种平衡的二叉排序树,树中任一结点的( ) A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过 1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 15.在 VSAM 文件的控制区间中,记录的存储方式为( ) A.无序顺序 B.有序顺序 C.无序链接 D.有序链接 3、某顺序存储的表格,其中有90, 000个元素,已按关键项的植的上升顺序排列。现假定对各个元素进行查 的概率是相同的, 并且各个元素的关键项的值皆不相同。 用顺序查找法查找时,平均比较次数约为_A_,最大比较次数为_B_。 现把90,000个元素按排列顺序划分成若干组,使每组有g个元素(最后一组可能不足g个) 。查找时, 先从第一组开始,通过比例各组的最后一个元素的关键项的值,找到欲查找的元素所在的组,然后再用顺 序查找法找到欲查找的元素。在这种查找法中,使总的平均比较次数最小的g是_C_,此时的平均比较次 数是_D_。当g的值大于等于90,000时,此方法的查找速度接近于_E_。 供选择的答案
第 58 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

A、B:①25,000 ②30,000 ③45,000 ④90,000 C、D:①100 ②200 ③300 ④400 E:①快速分类法 ②斐波那契查找法 ③二分法 ④顺序查找法 (试题2) 堆是一种特殊的数据结构,__A__是一个堆,堆排序是一种__B__排序,m个元素进行堆排序时,其时 间复杂性为__C__。 排序的算法很多,若按排序的稳定性和不稳定性分类,则__D__是不稳定排序。 外排序是指__E__。 供选择的答案 A:①19,75,34,26,97,56 ②97,26,34,75,19,56 ③19,56,26,97,34,75 ④19,34,26,97,56,75 B:①归并 ②交换 ③选择 ④插入 2 C:①o(m) ②o(m ) ③o(log2m) ④o(mlog2m) D:①冒泡排序 ②归并排序 ③直接插入排序 ④希尔(shell)排序 E:①用机器指令直接对硬盘中需排序数据排序 ②把需排序数据,用其他大容量机器排序 ③把外存中需排序数据一次性调入内存,排好序后,再输回外存 ④对外存中大于内存允许空间的需排序的数据,通过多次内外存间的交换实现排序。 试题6 堆是一种有用的数据结构。例如关键码序列_A_是一个堆。 堆排序是一种_B_排序, 它的一个基本问题是如何建堆,常用的建堆算法是1964 年 Floyd 提出的, _C_对含 n 个元素的序列进行排序时,?堆排序的时间复杂性是_D_,所需的附加存储结点是_E_。 供选择的答案 A: ①16, 72, 31, 23, 94, 53 ②94, 53, 31, 72, 16, 53 ? ③16, 53, 23, 94, 31, 72 ④16, 31, 23, 94, 53, 72 ? ⑤94, 31, 53, 23, 16, 72 ? B: ①插入 ②选择 ③交换 ④基数 ⑤归并 C: ①淘汰法 ②筛选法 ③递推法 ④LRU 算法 2 D、E:①O(nlog2n) ②O(n) ③O(log2n) ④O(n ) ? ⑤O(1) (试题1 ) 在排序算法中, 两两比较待排序的记录, 当发现不满意顺序要求时, 变更它们的相对位置, 这就是__A__ 排序。每次从未排序的记录中挑出最小(或最大)关键码值的记录,加入到已排序记录的末尾,这是__B__ 就组成一个堆,堆排序的平均执行时间和需附加的存储结点分别为__E__。 供选择的答案 A~C:① 插入 ② 枚举 ③ 交换 ④ 归并 ⑤ 基数 ⑥ 选择 ⑦ 希尔 D: ① 20、76、35、23、80、54 ② 20、54、23、80、35、76 ③ 80、23、35、76、20、54 ④ 20、35、23、80、54、76 2 E: ① O(n )和O(1) ② O(n log2 n)和O(1) 2 ③ O(n log2 n)和O(n) ④ O(n ) 和O(n) 23.若希望只进行 8 趟排序便能在 4800 个元素中找出其中值最小的 8 个元素,并且要求排序过程中所进 行的关键字比较次数尽可能少,则应该选用________________排序方法。 27.在待排序的 n 个记录中任取一个记录,以该记录的键值作为标准,将所有记录分为两组,使得第一组
第 59 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

中各记录的键值均小于或等于该键值,第二组中的各记录的键值均大于该键值;然后将该记录排在两组 中间。再对所分成的两组分别使用上述方法,直到所有记录都排在适当位置为止。这种排序方法称为 ________________。 28.在对一组记录关键字(54,38,96,23,15,72,60,45,83)进行冒泡排序时,整个冒泡排序过程 中需进行________________趟才能完成。 23.对关键字序列(52,80,63,44,48,91)进行一趟快速排序之后得到的结果为________。 24.由 10000 个结点构成的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度的最大值可能 达到________。 28.对关键字序列(72,87,61,23,94,16,05,58)进行堆排序,使之按关键字递减次序排列。请写出排 序过程中得到的初始堆和前三趟的序列状态。 初始堆:________ 第 1 趟:________ 第 2 趟:________ 第 3 趟:________ (3) 给定序列{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它一定( ⑤ )堆。 (4) 在进行直接插入排序时, 其数据比较次数与数据的初始排列( ⑥ )关;而在进行直接选择排序时, 其数据比较次数与数据的初始排列( ⑦ )关。 33.已知序列(503,87,512,61,908,170,897,275,653,462)请给出采用快速排序法作升序排序 时的每一趟的结果。 分) (8 29.已知 R[1..8]中的元素依次为(12,5,9,20,6,31,24,27) ,写出按算法 MergeSortDC 对 R 进行自顶向下的二路归并排序过程中,前 5 次调用函数 Merge(R, low, mid, high)时参数 low, mid 和 high 的值。 void MergeSortDC (int R[], int low, int mid, int high ) { int mid; if (low<high) { mid = (low +high)/2; MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high); Merge (R, low, mid, high); } } // MergeSortDC (1)第一次调用时的参数值; (2)第二次调用时的参数值; (3)第三次调用时的参数值; (4)第四次调用时的参数值; (5)第五次调用时的参数值; 33.已知整形数组 L[1..8]中的元素依次为(9,8,5,7,6,3,2,1) ,阅读下列函数,并写出执行函 数调用 sort(L, 8)时,对 L 进行的头两趟(pass 分别为 0 和 1)处理结果。 Void sort (int R[],int n) {
第 60 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

int pass = 0, k, exchange, x; do { k=pass%2+1; exchange = 0; while (k<n) { if (R[k]>R[k+1]) { x = R[k]; R[k] = R[k+1]; R[k+1] = x; exchange =1; } K+=2 } pass ++; }while (exchange = = 1|| pass <=1); } 第一趟(pass = 0): 第二趟(pass = 1): 34.已知二叉排序树中结点的关键字为整数,设计递归算法按递增有序性输出树中所有大于或等于给定值 x 的结点,并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构,其结点结构为: Lchild Key Rchild

33.已知序列(10,18,4,3,6,12,1,9,15,8) ,请给出采用二路归并排序法对该序列进行升序排 序时的每一趟结果。 分) (6 35.修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾,第二次把最小记 录放到表头,如此反复进行。试编写修改后的算法:void dbubble(int a[],int n)。 算法设计题 函数 void TraversalTree(BTREE *tree)用非递归方法,对以 tree 为根结点指针的二叉树进行后序遍历。 [函数 5,2] void TraversalTree(BTREE *tree) { BTREE *stack[1000],*p; int tag[1000],top=0; p=tree; do { while(p!=NULL){ stack[++top]=p; (3) ; tag[hop]=0; /*标志栈顶结点的左子树已进行过后序遍历*/ : } while(top>0 && (4) ){ /* 栈顶结点的右子树是否被后序遍历过*/ p=stack[top--];
第 61 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

putchar(p->data); } if (top>0) { /*对栈顶结点的右子树进行后序遍历*/ (5) ; tag[top]=1; } }while(top>0); }

附件:复习大纲
《数据结构》专升本复习大纲 一、考试要求: 1、能分析数据的内在逻辑关系。 2、掌握常用数据结构在计算机中的表示方法。 3、理解数据表示和数据处理之间的关系,理解算法效率的分析方法。 4、能利用常见的数据结构,进行算法设计。 二、考试内容 第 1 章 引论 1、了解数据结构的基本概念。 2、了解数据的逻辑结构、存储结构、算法的概念。 3、理解数据类型、抽象数据类型的概念。 4、理解时间复杂度、空间复杂度的概念。 5、理解数据结构二元组的概念。 S = <D,R> 第 2 章 线性表 1、理解 ADT 的概念及基本运算。 Abstract Data Type 2、掌握线性表的顺序存储结构及其运算的实现。 3、掌握线性表的链接存储结构及其运算的实现。 4、理解单链表、循环链表、双向链表的特点。 第3 章 栈 1、掌握栈的定义和基本运算。 2、掌握栈的顺序实现及其运算的实现。 3、掌握栈和队列的链接实现及其运算的实现。 4、掌握栈的应用。 (共享栈) (后缀表达式) (寄生栈) (括号匹配) (前中后缀转换) 5、理解递归的概念。 6、了解分治与递归的关系 7、了解用栈模拟递归技术。 第 4 章 队列 1、掌握队列的定义和基本运算。 2、掌握队列的顺序实现(循环队列)及其运算的实现。 3、掌握队列的链接实现及其运算的实现。 4、掌握队列的应用。 第 5 章 广义表 串 数组
第 62 页 共 63 页

济南铁道职业技术学院

专升本辅导教材

数据结构

1、广义表的概念 2、数组概念和应用 3、数组的压缩、稀疏矩阵、对称矩阵、对角矩阵 4、字符串的概念和相关操作 第6章 树 a)掌握树的存储表示,包括双亲表示法、孩子表示法、孩子兄弟表示法、树和二叉树的转换。 b)理解二叉树的定义和术语、性质。 c)掌握二叉树的存储结构,包括顺序存储、二叉链表。 d) 掌握二叉树的遍历算法及其应用。 e)了解线索树、平衡二叉树、B 树、B+树、B-树的概念。 F)掌握哈夫曼树及其应用 第7章 图 1、理解图的概念、术语。 2、掌握图的存储结构(邻接矩阵、邻接表、逆邻接表、十字链表表示) 3、掌握图的遍历方法(深度优先遍历、广度优先遍历) 4、掌握图的最小生成树的算法(prim 算法、kruskal 算法) 。 5、掌握图的单源最短路径的 dijkstra 算法。 5、了解所有顶点对之间的最短路径 floyd 算法。 第 8 章 排序与选择 1、 理解排序的基本概念(关键字、内外排序、稳定性、时间效率、空间效率) 2、 掌握选择排序的方法(简单选择排序、堆排序) 3、 掌握插入排序的方法(直接插入排序) 4、 掌握交换排序的方法(冒泡排序、快速排序) 5、 了解归并排序的方法。 6、 理解堆的概念及其实现。 7、 理解各种排序方法的优缺点。 第 9 章 查找和散列表 1、 了解散列表的概念。 2、 理解开散列表和闭散列表的实现。 3、 理解散列函数构造方法以及处理冲突的办法。 4、 掌握线性再散列技术。 5、 掌握各种静态查找技术和算法。 6、 掌握动态查找的概念、二叉搜索树、AVL 树 。

第 63 页 共 63 页


赞助商链接

更多相关文章:
国家普通话水平测试题注音版1-30套_图文
国家普通话水平测试题(1)一、读单音节字词(100 个音节,共 10 分,限时 3.5 ...也许正因为少,才在这次旅行之 中给我留下了很多美好的记忆。同时才使我至今...
普通话水平测试 最后一题
普通话水平测试 最后一题_其它考试_资格考试/认证_教育专区。我的愿望 每个人都...要学好普通话,首先,我觉得首先就要掌握正确的发音部,平常可以多练 习一下,而且...
2015年教师资格证考试普通话水平测试题一
2015 年教师资格证考试普通话水平测试题一 2015 下半年全国教师资格笔试在线估分_...他运用工程力 学的知识, 依据自己多年的实践, 巧妙地设计了只用一根柱子支撑的...
普通话水平测试朗读作品六十篇1(新大纲)
普通话水平测试朗读作品六十篇1(新大纲) - 1 普通话水平测试朗读作品六十篇(新大纲) 作品 1 号 那是力争上游的一种树,笔直的干,笔直的枝。它的干 呢,通常...
江苏省扬州市2015-2016学年高二下学期学业水平测试(必...
江苏省扬州市2015-2016学年高二下学期学业水平测试(必修)模拟考试(一)物理试题_...代表目前国地球同步轨道遥感 卫星最高分辨率水平.显著提升国用“天眼”看...
2018-2019年一年级下数学期末水平测试试卷
2018-2019年一年级下数学期末水平测试试卷 - 第二学期一年级期末水平测试试卷 姓名: 学号 评分 一、会填。 1、 请将计数器上的数位补充完整, 这个数写作 (...
四年级学业水平测试语文练习卷1
四年级学业水平测试语文练习卷1_语文_小学教育_教育专区。小学生学业水平测试练习...咪咪说,自己只有一 块钱,可不可以便宜一点呀。大猩猩高兴极了,赶快收下一块...
测一下你的财务分析水平是哪级
测一下你的财务分析水平是哪级_财务管理_经管营销_专业资料。测一下你的财务分析水平是哪级各位朋友,先做题再读后面的文字,然后再做题,效果最好!不做题,只读《...
焦虑症测试,测一你的焦虑水平
焦虑症测试,测一你的焦虑水平 - 成都军大医院 四川省精神卫生防治中心 400-075-2225 焦虑是一种人体的正常情绪反应,心理学家说,只要有回忆就有焦虑。只有过度...
2013学年第一学期天河区六年级语文期末水平测试参考答案
2013学年第一学期天河区六年级语文期末水平测试参考答案_语文_小学教育_教育专区...1.答案不唯一; 理解内容 2.把自己的理解写清楚,符合文本的内容即可得 1.5 分...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图