当前位置:首页 >> 其它课程 >>

2014-2015B学年二学期数据结构期末考试试卷(A卷)


石家庄学院
2014-2015 学年二学期数据结构期末考试试卷(A 卷) 班级:___________学号:___________姓名:___________得分:___________ 题号 得分 阅卷 题目部分,(卷面共有 94 题,397 分,各大题标有题量和总分) 一、应用题(5 小题,共 5 分) 1.线性表(a1,a2,…,an)用顺序映射表示时,ai 和 ai+1(1<=i<n〉的物理位置相邻吗?链 接表示时呢? 2.如何通过改链的方法,把一个单向链表变成一个与原来链接方向相反的单向链表? 3.如果已知森林的前序序列和后序序列分别为 ABCDEFIGJH 和 BDCAIFJGHE,请画出该森林 4.数据结构与数据类型有什么区别? 5.当你为解决某一问题而选择数据结构时,应从哪些方面考虑? 二、判断正误(20 小题,共 40 分) 1.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。( ) 2.顺序存储方式只能用于存储线性结构。( ) 3.若输入序列为 1,2,3,4,5,6,则通过一个栈可以输出序列 3,2,5,6,4,1. ( ) 4.两个栈共用静态存储空间,对头使用也存在空间溢出问题。 ( ) 5.栈和队列都是限制存取点的线性结构。 ( ) 6.通常使用队列来处理函数或过程的调用。 ( ) 7.用一维数组存储二叉树时,总是以前序遍历顺序存储结点。 ( ) 8. ( ) 二叉树中不存在度大于 2 的结点, 当某个结点只有一棵予树时无所谓左、 右子树之分。 9.后序线索二叉树是不完善的,要对它进行遍历,还需要使用栈。 ( ) 10. 若一个结点是某二叉树子树的前序遍历序列中的最后一个结点. 则它必是该子树中序遍 历序列中的最后一个结点。( ) 11.哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。( ) 12.程序一定是算法。( ) 13.数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。( ) 14.数据元素是数据的最小单位。( ) 15.数据结构的抽象操作的定义与具体实现有关。( ) 16.完全二叉树肯定是平衡二叉树。 ( ) 17.任何无环的有向图,其结点都可以排在一个拓扑序列里。 ( ) 18.最优二叉搜索树一定是平衡的二叉搜索树。 ( ) 19.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。 ( ) 20.堆排序占用的辅助空间很大。 ( ) 三、单项选择题(20 小题,共 60 分) 1.在一个长度为 n 的顺序表中,在第 i 个元素(1≤i≤n+1)之前插入一个新元素时须向后移 动( )个元素 A、n-i B、n- i+l C、n-i-1 D、 i 2.将两个各有 n 个元素的有序表归并成一个有序表.其最少的比较次数是 A、n B、2n-1 C、2n D、n-1 一 二 三 四 五 六 七 八 九 十 成绩 复核

3. 在一个具有 n 个结点的有序单链表中插入一个新结点, 并使插入结点后的单链表仍然有 序,则该操作的时间复杂性量级为。 A、.0 ( 1 ) B、 0 ( n ) C、 0 ( nlog2n ) D、 0 ( n2 ) 4.在一个以 h 为头的单循环链中,p 指针指向链尾的条件是 A、 p^.next=h B、 p^.next=NIL C、 p^.next.^next=h D、 p^.data=-1 5.(1) 静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第 i 个元素 的时间与 i 无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。 以上错误的是 A、 B、 C、 D、 (1) , (2) (1) (1) , (2),(3) (2) 6.对于一个头指针为 head 的带头结点的单链表,判定该表为空表的条件是 A、head==NULL B、head→next==NULL C、head→next==head D、head!=NULL 7.同一个栈内各元素的类型。 A、 必须一致 B、 可以不一致 C、 不能一致 D、 不必不一致 8.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点, 则在进行删除操作时 A.仅修改队头指针 B、 仅修改队尾指针 C、队头、队尾指针都要修改 D、 队头,队尾指针都可能要修改 9.顺序栈是空栈的条件是。 A、 top==0 B、 top==1 C、 top==-1 D、 top==m 10.串是一中特殊的线性表,其特殊性体现在。 A、 可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、 数据元素可以是多个字符 11.设树 T 的高度为 4,其中度为 l、2、3 和 4 的结点个数分别为 4、2、1、1,则 T 中的叶 子数为 A、5 B、6 C、7 D、8 12.某义树的前序序州和后序序列正好相反.则泼二叉树一定是( )的一叉树。 A、空或只有一个结点 B、任一结点无左于树 C、高度等于其结点数 D、任一结点无右子树 13.一个具有 1025 个结点的二叉树的高 h 为 A、11 B、10 C、11 至 1025 之间 D、10 至 1024 之间 14.若度为 m 的哈夫曼树中,其叶结点个数为 n,则非叶结点的个数为 A、n-1 B、?n/m?-1 C、?(n-1)/(m-1)? D、 ?n/(m-1)?-1 E、?(n+1)/(m+1)?-1 15.设森林 F 对应的二叉树为 B,它有 M 个结点,B 的根为 P,P 的右子树结点个数为 N, 森林 F 中第一棵树的结点个数是 A、M-N B、M-N-1 C、N+1 D 条件小充分,无注确定 16.程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与 A[j+1]对换; 其中 n 为正整数,则最后一行的语句频度在最坏情况下是

A. O(n) B、 O(nlogn) C、O(n3) D、O(n2) 17.以下数据结构中, ( )是非线性数据结构 A、树 B、字符串 C、队 D、栈 18.以下数据结构中,哪一个是线性结构? A、广义表 B、 二叉树 C、稀疏矩阵 D、 串 19.在计算机中存储一个数据元素的位串称为。 A、 结点 B、 数据项 C、 数据字段 D、 字符串 20.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是 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) 四、算法设计题(5 小题,共 20 分) 1.已知不带头结点的线性链表 list,链表中结点构造为(data、link) ,其中 data 为数据域, link 为指针域。请写一算法,将该链表按结点数据域的值的大小从小到大重新链接。要求链 接过程中不得使用除该链表以外的任何链结点空间。 2.写一个算法,求出循环链表结点的个数。 (不包括头结点) 3.试编写算法,将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式 中各自仅含奇次项或者偶次项,并要求利用原链表中的结点空间构成这两个链表。 4.试利用循环队列编写 k 阶斐波那契序列中前 n+1 项(f0,f1,…,fn)的算法,要求满足: Fn max 而 fn+1>max,其中 max 为某个约定的常数。 (注意:本题所用循环队列的容量仅为 k, 则在算法执行结束后时,留在循环队列中的元素应是所求 k 阶斐波那契序列中的最后 k 项 (fn-k+1,…,fn) 。 5.建立三元组存储方法 五、多项选择题(10 小题,共 50 分) 1.表长为 n 的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插 入一个元素所需移动的元素平均个数为( ) ,删除一个元素所需移动的平均个数为 A、(n-1)/2 B、n C、n+1 D、 n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 2.下面的叙述不正确的是 A、线性表在链式存储时,查找第 i 个元素的时间同 i 的值成正比 B、线性表在链式存储时,查找第 i 个元素的时间同 i 的值无关 C、线性表在顺序存储时,查找第 i 个元素的时间同 i 的值成正比 D、线性表在顺序存储时,查找第 i 个元素的时间同 i 的值无关 3.在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈 中元素为 n 个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将 两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时,才产生上溢。 B、 满 C、 上溢 D、 下溢 ①, ②: A、 空 B、 n C、 n+1 D、 n/2 ③: A、 n-1 B、 深度 C、 栈顶 D、 栈底 ④: A、 长度 ⑤: A、 两个栈的栈顶同时到达栈空间的中心点. B、 其中一个栈的栈顶到达栈空间的中心点. C、 两个栈的栈顶在栈空间的某一位置相遇.

D、 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 4.一个输入序列 abcd 经过一个栈到达输出序列,并且一旦离开输出序列后就不能再返回到 输入序列,则下面( )为正确的输出序列。 A、 bcad B、cbda C、dabc D、acbd E、dcba 5.两个串相等必有 A、串长度相等 B、串中各位置字符任意 C、串中各位置字符均对应相等 D、串长度不等 E、串长度任意 6. nexrval 数组的值为 模式串 T='abcaabbcabcaabdab’ , 该模式串的 next 数组值为 ( ) , ( ) 。 A、01112211123456712 B、011121 21124567112 C、01110013101100701 D、01112231123456712 E、01100111011001702 F、01102131011021701 7.对于前序遍历与中序遍历结果相同的二叉树为(1); 对于前序遍历和后序遍历结果相同的二叉树为(2) 。 A、一般二叉树 B、只有根结点的二叉树 C、根结点无左孩子的二叉树 D、根结点无右孩子的二叉树 E、所有结点只有左子数的二叉树 F、所有结点只有右子树的二叉树 8.从下列有关树的叙述中,选出 5 条正确的叙述 A、二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。 B、当 K≥1 时高度为 K 的二叉树至多有 2k-1 个结点。 C、用树的前序周游和中序周游可以导出树的后序周游。 D、线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 E、将一棵树转换成二叉树后,根结点没有左子树。 F、一棵含有 N 个结点的完全二叉树,它的高度是?LOG2N?+1。 G、在二叉树中插入结点,该二叉树便不再是二叉树。 H、 采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一 样的。 I、哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 J、用一维数组存储二叉树时,总是以前序周游存储结点。 9.若采用链地址法构造散列表,散列函数为 H(key)=key MOD 17,则需 ((1)) 个链表。 这些链的链首指针构成一个指针数组,数组的下标范围为 ((2)) B、 13 C、 16 D、 任意 (1) A、17 B、 1 至 17 C、 0 至 16 D、 1 至 16 (2) A、0 至 17 10.要进行顺序查找,则线性表(1) ;要进行折半查询,则线性表(2) ;若表中元素个数为 n,则顺序查找的平均比较次数为(3) ;折半查找的平均比较次数为(4) 。 (1) (2) : A、 必须以顺序方式存储; B、 必须以链式方式存储; C、 既可以以顺序方式存储,也可以链式方式存储; D、 必须以顺序方式存储,且数据已按递增或递减顺序排好; E. 必须以链式方式存储,且数据已按递增或递减的次序排好。 (3) (4) : A、n B、n/2 C、n*n D、n*n/2 E.log2n F.nlog2n G.(n+1)/2 H.log2(n+1) 六、填空题(20 小题,共 120 分) 1.已知指针 p 指向单链表 L 中的某结点,则删除其后继结点的语句是:________

2.单链表表示法的基本思想是用_______表示结点问的逻辑关系。 3.在线性表的顺序存储中,元素之间的逻辑关系是通过______决定的;在线性表的链式存 储中,元素之间的逻辑关系是通过_______决定的。 4. 用下标 0 开始的 N 元数组实现循环队列时, 为实现下标变量 M 加 1 后在数组有效下标范 围内循环,可采用的表达式是:M:=_______(填 PASCAL 语言,C 语言的考生不填) ; M= _______(填 C 语言,PASCAL 语言的考生不填) 。 5.设循环队列用数组 A[1..M]表示,队首、队尾指针分别是 FRONT 和 TAIL,判定队满的条件 为_______。 6._______是限定仅在表尾进行插入或删除操作的线性表。 7.设正文串长度为 n,模式串长度为 m,则串匹配的 KMP 算法的时间复杂度为_______。 8.两个串相等的充分必要条件是_____________________。 9.若二叉树有 N 个结点,对它分别进行前序遍历、中序遍历、后序遍历时,开辟的栈分别 为___________个存储单元、_______个存储单元、___________个存储单元。 10.8 层完全二叉树至少有_____个结点.拥有 100 个结点的完全二叉树的最大层数为____。 11.设 为哈夫曼树的叶子结点数目.则哈夫曼树共有_______个结点。 12. k 深度为 k (设根的层数为 1)的完全二叉树至少有_______个结点, 至多有______个结点. 和结点数 n 之间的关系足_________. 13.如下图为某树的静态双亲链表表示,则结点 D、E 积亲结点分别为____________。

14.如果结点 A 有 3 兄弟,而且 B 是 A 的双亲,则 B 的度是__________。 15.已知一棵度为 3 的树有 2 个度为 1 的结点,3 个度为 2 的结点,4 个度为 3 的结点,则 该树有______个叶子结点。 16.下面程序段的时间复杂度为________。(n>1) sum=1; for (i=0;sum<n;i++) sum+=1; 17.下面程序段中带下划线的语句的执行次数的数量级是_______。 i:=1; WHILE i<n BEGIN FOR j:=1 TO n DO_x:=x+1;i:=i*2 END; 18.已知如下程序段 FOR i:= n DOWNTO 1 DO {语句 1} BEGIN x:=x+1; {语句 2} FOR j:=n DOWNTO i DO {语句 3} y:=y+1; {语句 4} END; 语句 1 执行的频度为__________;语句 2 执行的频度为__________ ;语句 3 执行的频度为 __________;语句 4 执行的频度为___________。 19.数据的物理结构包括_________的表示和_________的表示。 20.对于具有 144 个记录的文件,若采用分块查找法,且每块长度为 8,则平均查找长度为 __________. 七、简答题(10 小题,共 70 分) 1.何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

简述线性表的相互许存储与链接存储的空间分配方式、存储结构特性和主要优缺点。 2.为什么在单循环链表中设置尾指针比设置头指针更好? 3.在单链表、双链表和单循环链表中,若仅知道指针 p 指向某结点,不知道头指针,能否 将结点*p 从相应的链表中删去?若可以,其时间复杂度各为多少? 4.循环队列的优点是什么? 如何判别它的空和满? 5.对于循环向量中的循环队列,写出求队列长度的公式。 6.如果一棵 Huffman 树 T 有 个叶子结点,那么,树 T 有多少个结点? 7.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别? 8.什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 9.什么是算法? 算法的 5 个特性是什么? 试根据这些特性解释算法与程序的区别。 10.线性表可用顺序表或链表存储。试问: (1) 两种存储表示各有哪些主要优缺点? (2) 如果有 n 个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可 能自动改变、在此情况下,应选用哪种存储表示?为什么? (3) 若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素, 这时,应采用哪种存储表示?为什么? 八、名词解释(4 小题,共 32 分) 1.队列 2.栈。 3.串 4.伙伴空间

石家庄学院
2014-2015 学年二学期数据结构期末考试试卷(A 卷) 答案部分,(卷面共有 94 题,397.0 分,各大题标有题量和总分) 一、应用题(5 小题,共 32 分) 1.顺序映射时,ai 与 ai+1 的物理位置相邻;链表表示时 ai 与 ai+1 的物理位置不要求相邻。 2.本题是链表的逆置问题。设该链表带头结点,将头结点摘下,并将其指针域置空。然后 从第一元素结点开始,直到最后一个结点为止,依次前插入头结点的后面,则实现了链表的 逆置。 3.由于森林的前序序列与其对应的二叉树前序序列相同,而森林的后序序列与其对应的二 叉树中序序列相同。 因此, 根据二叉树前序序列 ABCDEFIGJH 和中序序列 BDCAIFJGHE 可画出 二叉树如下图所示。

而由上图的二叉树转化为的森林如下图所示。

4. “数据结构” 这一术语有两种含义, 一是作为一门课程的名称; 二是作为一个科学的概念。 作为科学概念,目前尚无公认定义,一般认为,讨论数据结构要包括三个方面,一是数据的 逻辑结构,二是数据的存储结构,三是对数据进行的操作(运算) 。而数据类型是值的集合 和操作的集合,可以看作是已实现了的数据结构,后者是前者的一种简化情况。 5.通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面:程序 运行时所需输入的数据总量, 对源程序进行编译所需时间, 计算机执行每条指令所需时间和 程序中指令重复执行的次数。 二、判断正误(20 小题,共 32 分) 1.√ 2.× 3.√ 4.√ 5.√ 6.× 7.× 8.× 9.√ 10.× 11.√ 12.× 13.√ 14.× 15.×

16.× 17.√ 18.√ 19.√ 20.× 三、单项选择题(20 小题,共 32 分) 1.B 2.A 3. B 4. A 5. B 6. B 7. A 8. D 9. C 10. B 11. D 12. A 13. C 14.C 15. A 16. D 17. A 18. D 19. A 20. C 四、算法设计题(5 小题,共 32 分) 1.[题目分析]本题实质上是一个排序问题,要求“不得使用除该链表结点以外的任何链结 点空间” 。链表上的排序采用直接插入排序比较方便,即首先假定第一个结点有序,然后, 从第二个结点开始,依次插入到前面有序链表中,最终达到整个链表有序。 LinkedList LinkListSort(LinkedList list) data 是数据域, link ∥list 是不带头结点的线性链表, 链表结点构造为 data 和 link 两个域, 是指针域。本算法将该链表按结点数据域的值的大小,从小到大重新链接。 {p=list->link; ∥p 是工作指针,指向待排序的当前元素。 list->link=null;∥假定第一个元素有序,即链表中现只有一个结点。 while(p!=null) {r=p->link; ∥r 是 p 的后继。 q=list; if(q->data>p->data)∥处理待排序结点 p 比第一个元素结点小的情况。 {p->link=list; list=p;∥链表指针指向最小元素。 } else∥查找元素值最小的结点。

{while(q->link!=null&&q->link->data<p->data)q=q->link; p->link=q->link;∥将当前排序结点链入有序链表中。 q->link=p; } p=r;∥p 指向下个待排序结点。 } } [算法讨论]算法时间复杂度的分析与用顺序存储结构时的情况相同。但顺序存储结构将第 i(i>1)个元素插入到前面第 1 至第 i-1 个元素的有序表时, 是将第 i 个元素先与第 i-1 个元素比 较。 而在链表最佳情况均是和第一元素比较。 两种存储结构下最佳和最差情况的比较次数相 同,在链表情况下,不移动元素,而是修改结点指针。 另一说明是,本题中线性链表 list 不带头结点,而且要求“不得使用除该链表以外的任何 链结点空间“,所以处理复杂,需要考虑当前结点元素值比有序链表第一结点的元素值还小 的情况,这时要修改链表指针 list。如果 list 是头结点的指针,则相应处理要简单些,其算 法片段如下: p=list->link;∥p 指向第一元素结点。 list->link=null;∥有序链表初始化为空 while(p!=null) {r=p->link;∥保存后继 q=list; while(q->link!=null && q->link->data<p->data)q=q->link; p->link=q->link; q->link=p; q=r; } 2.为了运算的方便,设该循环链表为带头结点的链表。本题关键是确定循环终.p 从第一 个结点出发,每检测一个结点,计数器加 1。当表尾结点被检测计数以后 继续往后移动,则回到了头结点,此时终止循环。算法如下: int count(LinkList head) { int n=0; ListNode。p=head 一>next; while(p!=head) { n++;P=P?next;} return n; } 3. void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式 L 拆成只含奇 次项的 A 和只含偶次项的 B { p=L->next; A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) {

if(p->data.exp!=2*(p->data.exp/2)) { pa->next=p;pa=p; } else { pb->next=p;pb=p; } p=p->next; }//while pa->next=A;pb->next=B; }//Divide_LinkedPoly 4.void GetFib_CyQueue(int k,int n)//求 k 阶斐波那契序列的前 n+1 项 { InitCyQueue(Q); //其 MAXSIZE 设置为 k for(i=0;i<k-1;i++) Q.base[i]=0; Q.base[k-1]=1; //给前 k 项赋初值 for(i=0;i<k;i++) printf("%d",Q.base[i]); for(i=k;i<=n;i++) { m=i%k;sum=0; for(j=0;j<k;j++) sum+=Q.base[(m+j)%k]; Q.base[m]=sum; //求第 i 项的值存入队列中并取代已无用的第一项 printf("%d",sum); } }//GetFib_CyQueue 5.输入一个稀疏矩阵 A 建立三元组存储方法的函数如下: void crt_matrix(A,B) int A[m][n]; smatrik B;/*A 是一个稀疏矩阵,B 是产生的相对应的三元组*/ { int i,j,k=1; for(i=0;i<n;i++)/*按行优先顺序扫描 A 的元素,不为 0 者存入 B 中*/ for(j=0;j<m;j++) if(A[ i ][ j ]!=0) { B[k][0]= i; B[k][1]= j; B[k][2]= A[ i ][ j ]; k++; } B[0][0]= m; B[0][1]= n;

B[0][2]= k-1;/*存入非 0 元素个数*/ } 五、多项选择题(10 小题,共 32 分) 1. E A 2. B,C 3.①B ②A ③B ④D ⑤C 4.ABDE 5.AC 6.D,F 7.1F2B 8.C D F H I 9.1A 2C 10.1C 2D 3G 4H 六、填空题(20 小题,共 32 分) 1. u=p->next; p->next=u->next; free(u); 2.指针 3.物理存储位胃;链指针 4.(M+1) MOD N (M+1)% N; 5. (TAIL+1)MOD M=FRONT (数组下标 0 到 M-1,若一定使用 1 到 M,则取模为 0 者,值改 取M 6.栈 7. O(n+m) 8.两个串的长度相等且对应位置的字符相同 9.三种遍历使用栈的深度均为树高 h,故填:O(h)。 10.8 层完全二叉树具有最少结点的情况是前 7 层为满二叉树而第 8 层仅有一个结点,即为 - 1 + 1 = 128,同时也看出具有 100 个结点的完全二叉树的最大层数为 7 层,故填:128 , 7。 11. -1 12. 13.B C 14. 4 15.12 16. O(n) 17. nlog2n 18.n+1 n n(n+3)/2 n(n+1)/2。 19.数据元素 数据元素间关系 20.14 七、简答题(10 小题,共 32 分) 1.顺序表的最大优点是可随机访问,因此,如果对线性表经常进行查找、排序 等运算,则宜采用顺序表作为存储结构。 链表的最大优点是便于插入和删除(它不需要移动元素,只需要修改指针)。因此, 如果对线性表经常进行插、删运算,则宜采用链表作为存储结构。

2.尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和 终端结点都很方便,设一带头结点的单循环链表,其尾指针为 rear,则开始结点和终端结点 的位置分别是 rear->next->next 和 rear, 查找时间都是 O(1)。 若用头指针来表示该链表,则查找终端结点的时间为 O(n)。 3.分别讨论三种链表的情况。 ⑴ 单链表。当我们知道指针 p 指向某结点时,能够根据该指针找到其直接后继,但是由于 不知道其头指针,所以无法访问到 p 指针指向的结点的直接前趋。因此无法删去该结点。 ⑵ 双链表。由于这样的链表提供双向链接,因此根据已知结点可以查找到其直接前趋和直 接后继,从而可以删除该结点。其时间复杂度为 O(1)。 ⑶ 单循环链表。根据已知结点位置,我们可以直接得到其后相邻的结点位置(直接后继), 又因为是循环链表,所以我们可以通过查找,得到 p 结点的直接前趋。因此可以删去 p 所指 结点。其时间复杂度应为 O(n)。 4.循环队列的优点是:它可以克服顺序队列的"假上溢"现象,能够使存储队列的向量空间 得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定,一般是通过 以下几种方法:一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次 入队前测试入队后头尾指针是否会重合, 如果会重合就认为队列已满。 三是设置一计数器记 录队列中元素总数,不仅可判别空或满,还可以得到队列中元素的个数。 5.公式如下(设采用第二种方法,front 指向真正的队首元素,rear 指向真正队尾后一位置, 向量空间大小:QueueSize Queuelen=(QueueSize+rear-front)%QueueSize 6.因为 Huffman 树没有度为 1 的结点,所以树 T 有 2 -1 个结点 7.简单来说,数据结构定义了一组按某些关系结合在一起的数据元素;抽象数据类型是指 一个数学模型以及定义在该模型上的一组操作; 而程序设计语言中的数据类型不仅定义了一 组带结构的数据元素,而且还在其上定义了一组操作。 8.数据结构是指数据以及相互之间的关系。记为:数据结构 = { D, R }。其中,D 是某一数 据对象,R 是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容: ① 数据成员以及它们相互之间的逻辑关系,也称为数据的逻辑结构,简称为数据结构; ② 数据成员极其关系在计算机存储器内的存储表示,也称为数据的物理结构,简称为存储 结构; ③ 施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据, 它与数据的存储不是一码事, 是与计算机存储无 关的。因此,数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型,是数据的应用 视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像) ,它是依赖 于计算机的,是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算,每种数 据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 9.通常,定义算法为"为解决某一特定任务而规定的一个指令序列。"一个算法应当具有以 下特性: ① 有输入。一个算法必须有 0 个或多个输入。它们是算法开始运算前给予算法的量。这些 输入取自于特定的对象的集合。 它们可以使用输入语句由外部提供, 也可以使用赋值语句在 算法内给定。 ② 有输出。一个算法应有一个或多个输出,输出的量是算法计算的结果。 ③ 确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况,需要执行的动作 都应严格地、清晰地规定。

④ 有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。 ⑤ 有效性。算法中每一条运算都必须是足够基本的。就是说,它们原则上都能精确地执行, 甚至人们仅用笔和纸做有限次运算就能完成。 算法和程序不同,程序可以不满足上述的特性(4) 。例如,一个操作系统在用户未使用前一 直处于"等待"的循环中,直到出现新的用户事件为止。这样的系统可以无休止地运行,直到 系统停工。 此外,算法是面向功能的,通常用面向过程的方式描述;程序可以用面向对象方式搭建它的 框架。 10. (1) 顺序存储表示是将数据元素存放于一个连续的存储空间中, 实现顺序存取或(按下标) 直接存取。它的存储效率高,存取速度快。但它的空间大小一经定义,在程序整个运行期间 不会发生改变,因此,不易扩充。同时,由于在插入或删除时,为保持原有次序,平均需要 移动一半(或近一半)元素,修改效率不高。 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放, 且只要存储器中还有空 间, 就不会产生存储溢出的问题。 同时在插入和删除时不需要保持数据元素原来的物理顺序, 只需要保持原来的逻辑顺序, 因此不必移动数据, 只需修改它们的链接指针, 修改效率较高。 但存取表中的数据元素时,只能循链顺序访问,因此存取效率不高。 (2) 如果有 n 个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可 能自动改变、在此情况下,应选用链接存储表示。 如果采用顺序存储表示, 必须在一个连续的可用空间中为这 n 个表分配空间。 初始时因不知 道哪个表增长得快,必须平均分配空间。在程序运行过程中,有的表占用的空间增长得快, 有的表占用的空间增长得慢; 有的表很快就用完了分配给它的空间, 有的表才用了少量的空 间,在进行元素的插入时就必须成片地移动其他的表的空间,以空出位置进行插入;在元素 删除时,为填补空白,也可能移动许多元素。这个处理过程极其繁琐和低效。 如果采用链接存储表示,一个表的存储空间可以连续,可以不连续。表的增长通过动态存储 分配解决, 只要存储器未满, 就不会有表溢出的问题; 表的收缩可以通过动态存储释放实现, 释放的空间还可以在以后动态分配给其他的存储申请要求,非常灵活方便。对于 n 个表(包 括表的总数可能变化)共存的情形,处理十分简便和快捷。所以选用链接存储表示较好。 (3) 应采用顺序存储表示。因为顺序存储表示的存取速度快,但修改效率低。若表的总数基 本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时采用顺序存储 表示较好。 八、名词解释(4 小题,共 32 分) 1.队列是允许在一端插入而在另一端删除的线性表,允许插入的一端叫队尾,允许删除的 一端叫队头。最先插入队的元素最先离开(删除) ,故队列也常称先进先出(FIFO)表。 2.栈是只准在一端进行插入和删除操作的线性表,允许插入和删除的一端叫栈顶,另一端 叫栈底。最后插入的元素最先删除,故栈也称后进先出(LIFO)表。 3.串是零个至多个字符组成的有限序列。从数据结构角度讲,串属于线性结构。与线性表 的特殊性在于串的元素是字符。 4.在伙伴系统中,无论占用块或空闲块,其大小均为 2 的 k(k 为≥0 的正整数)次幂。若内 存容量为 2m,则空闲块大小只能是 20,21,22,…,2m。由同一大块分裂而得的两个小 块互称“伙伴空间” ,如内存大小为 210 的块分裂成两个大小为 29 的块。只有两个“伙伴空 间”才能合并成一个大空间。 起始地址为 p,大小为 2k 的内存块,其伙伴的起始地址为: buddy(p,k)=p+2k (若 p % 2k+1=0),或 buddy(p,k)=p-2k (若 p % 2k+1=2k)

试卷指标统计数据 总题量 94 总分值 397

章节编码 题量 分值 章节说明 01 02 03 05 10 11 12 13 14 17 难度编码 1 2 3 题型编码 01 02 03 04 05 06 07 08 21 17 6 21 17 1 5 4 1 1 85 79 33 85 67 8 21 8 7 4 线性表及其顺序存储 顺序表 栈和队列 串 树和二叉树、森林 绪论 动态存储管理 集合 数据结构试题 链表 字符串、数组和特殊矩阵 题量 70 14 10 题量 5 20 20 5 10 20 10 4 分值 297 62 38 分值 5 40 60 20 50 120 70 32 难度说明 易 中 难 题型说明 应用题 判断正误 单项选择题 算法设计题 多项选择题 填空题 简答题 名词解释


赞助商链接
相关文章:
更多相关标签: