国家开放大学电大本科数据结构期末题库及答案

1、最新国家开放大学电大本科 数据结构 期末题库及答案考试说明： 本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。做考题时，利用本文档中的查 TOC o 1-5 h z 找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。本文库还有其他网核 及 教学考一体化答案 ，敬请查看。数据结构题库及答案一( 每小题 2 分。共 l8 分)下面程序段的时间复杂度为 ( )。for(int i=0； im ； i+)for(int j=0； jlink=S ；s link=top link

2、 ; top link=S ;C S-link=top； top S；D . s link=top ; top top - link ;一棵具有35 个结点的完全二叉树的高度为 ( ) 。假定空树的高度为一l 。A 5 B 6C7 D8向具有 n 个结点的堆中插入一个新元素的时间复杂度为 ( )。A O(1) B 0(n)C O(log 2n)D O(nlog 2n).在一棵AVL树中，每个结点的平衡因子的取值范围是()。A. l 1 B . 22C . 12 D. O1一个有 n 个顶点和 n 条边的无向图一定是( ) 的。A.连通 B .不连通C 无回路D 有回路( 每小题 2 分，共 l

3、4 分)1 数据结构包括() 、存储结构和对数据的运算这三个方面。一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的() 存取的。将一个n 阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该一维数组需要至少具有() 个元素。对于一棵具有n 个结点的树，该树中所有结点的度数之和为 () 。在一棵高度为 3 的理想平衡二叉树中，最少含有() 个结点，假定树根结点的高度为 0 。假定对长度n=50 的有序表进行折半搜索，则对应的判定树中最底层的结点数为 () 个。用邻接矩阵存储图，占用的存储空间与图中的 () 数有关。三、判断题。在每小题前面打对号表示正确或打叉号表

4、示错误(每小题 2 分。共 14 分)()1算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。( )2 用字符数组存储长度为 n 的字符串，数组长度至少为 n+1。()3在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。( )4 邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。( )5 对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。 ( )6 在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。 ( )7 图中各个顶点的编 号是人为的，不是它本身固有的，因此可以根据需要进行改变。四、运算题 ( 每小题

5、6 分，共 30 分)1 假定一棵二叉树广义表表示为 a(b(c) ， d(e ， f) ，分别写出对它进行中序、后序、按层遍历的结果。中序：后序：按层:如有你有帮助，请购买下载，谢谢！ 2 . 一个一维数组 all2中存储着有序表(15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 80, 86),根据折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成功搜索时的平均搜索长度。度为l的结点个数：平均搜索长度：.假定一个线性序列为(38, 42, 55, 15, 23, 44, 30, 74, 48, 26),根据此线性序列中元素的排

6、列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空的所有单支结 点和所有叶子结点，请按照结点值从小到大的次序写出。左子树为空的所有单支结点： 右子树为空的所有单支结点： 所有叶子结点：.已知一个图的顶点集V和边集G分别为：V=1 , 2, 3, 4, 5, 6;E=, , , , , , , , ;假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次 序链接的，试写出：(1)从顶点l出发进行深度优先搜索所得到的顶点序列；(2)9,N点1出发进行广度优先搜索所得到的顶点序列。(1):(2)5.已知一个数据序列为16, 45, 27, 23,

7、41 , 15, 56, 64,请把它调整为一个最大堆。最大堆： 五、算法分析题(每小题6分。共12分)下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅 读算法，在划有横线的上面填写合适的内容。ListNode*Mergel(ListNode* . & pl , ListNode*&p2) ListNode*p=new ListNode , *f=p ;while(p1!=NULL & p2!=NULL) if(pl-datadata) p-link=pl ； ;elsep-link=p2 ; p2=p2 一link ; )if(pl!=NULL)p-link=pl

8、; else p 1ink=p2 ;pl=p2=NULL;return f 一 link :2 已知二叉树中的结点类型BinTreeNode 定义为：struct BinTreeNodeElemType data ； BinTreeNode*left ， *right ； ；其中 data 为结点值域， left 和 right 分别为指向左、右子女结点的指针域。根据下面算法的定义指出其功能。算法中参数BT 指向一棵二叉树。BinTreeNode*BTreeSwopX(BinTreeNode*BT)if(BT= =NULL)return NULL ；elseBinTreeNode*pt=new

9、 BinTreeNode ；pt -dataBT-data ;pt right BTreeSwopX(BTleft);pt 一 left=BTreeSwopX(BT-right)；return pt ；算法功能：六、算法设计题 ( 每小题 6 分，共 12 分)已知 f 为单链表的表头指针，单链表中的结点结构为 (data ， link) ，并假定每个结点的值均为大于 0 的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值 0。int Max(LinkNode*f) ；设Q 是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明写出从此队

10、列中删除一个元素的算法。循环队列定义struct CyclicQueueElemType elemEM ;/ M为已定义过的整型常量int rear ； rear 指向队尾元素的后一个位置int length ： length 指示队列中元素个数5若队列非空则删除队头元素并由引用参数 x 带回， 同时返回 true ； 否则若队列为空则返回 false5页ElemType&x)；bool DelCQueue(CyclicQueue Q试题答案及评分标准一、单项选择题，翟括号内填写所选择的标号（ 每小题 2 分，共 18 分）1 C 2 C 3 B 4 B 5 C6 A 7 C 8 A 9 b二

11、、填空题。在横线处填写合适内容（ 每小题 2 分，共 14 分）1 逻辑结构 2 下标 （或顺序号 ） 3 n（n+1） 2 4 n 一 1 5 8 6 19 7 顶点三、判断题，在每小题前面打对号表示正确或打叉号表示错误（ 毒小题 2 分。共 14 分 ）1 错2 对 3 对 4 错5 对6错 7 对 7 对四、运算题 （ 每小题 6 分，共 30 分 ）中序：C， b， a， e ， d， f后序：C，b，e，f ，d ，a按层：a ，b，d，C，e ，f度为1 的结点个数： 5平均搜索长度： 37/12左子树为空的所有单支结点：l5 ， 23， 42， 44右子树为空的所有单支结点： 3

12、0所有叶子结点： 26， 48 ， 74 （I）1 ，2，4，5， 3，6 3分（2）1 ， 2 ，3 ，4，5， 63 分最大堆： 64 ， 45， 56， 23， 41， 15， 27， 16五、算法分析题 （ 每小题 6 分。共 12 分）. pl2p1 link、p=p link /每空 3 分生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT 中所有结点的左、右子树 （ 或左、右孩子的值） 交换的结果。六、算法设计题 （ 每小题 6 分。共 12 分）评分标准：按注释酌情给分。int Max（LinkNode*f）if（f= =NULL）return 0：if（f 一 link

13、= =NULL）return f 一 data ；int temp=Max(f-link)；if(f 一 datatemp)return f 一 data ；else return temp ；2评分标准：按注释酌情给分：bool DelCQueue(CyelieQueue Q ， ElemType&x)if(Q 1ength= =O)return false ；x Q elem(Q rear Q 1ength-t-M) M；Q 1ength 一 一；return true ；数据结构题库及答案二一、单项选择题 ( 每小题 2 分。共 30 分)链表所具备的特点是( ) 。A 可以随机访问任一

14、结点B 占用连续的存储空间C 插入删除元素的操作不需要移动元素结点D 可以通过下标对链表进行直接访问线性结构中数据元素的位置之间存在( ) 的关系。A 一对一B 一对多C 多对多D 。每一个元素都有一个直接前驱和一个直接后继算法的时间复杂度与( ) 有关。 7A 所使用的计算机B 与计算机的操作系统C 与算法本身 D 与数据结构在一个单链表中，p、 q 分别指向表中两个相邻的结点，且q 所指结点是P 所指结点的直接后继，现要删除 q 所指结点，可用的语句是( ) 。A p=q-next B p-next=qC p-next=q-next D q-next=NULL TOC o 1-5 h z

15、在一个链队中，假设f 和 r 分别为队头和队尾指针，则删除一个结点的运算为 ( )。A r=f-next ：Br=r-next ：Cf=f 一 next；Df=r 一 next：元素 3 ， 6 ， 9 按顺序依次进栈，则该栈的不可能输出序列是( )( 进栈出栈可以交替进行) 。A9，6 ，3B9，3 ，6C6，3 ，9D3，9 ，6.设有一个10阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组中(数组下标从1 开始 ) ，则矩阵中元素氏， 。在一维数组B 中的下标是( ) 。A33B32C85D41在 C 语言中，顺序存储长度为 3 的字符串，需要占用 ( ) 个字

16、节。A4 B3C6 D12一棵有 n 个结点采用链式存储的二叉树中，共有( ) 个指针域为空。A n+1 B nC n 一 1 D n-2设一棵哈夫曼树共有n 个叶结点，则该树有( ) 个非叶结点。A n 1 B nC n+1 D 2n在一个无向图中，所有顶点的度数之和等于边数的 ( ) 倍。A 3 B 2 5C 1 5 D 2.已知如图1所示的一个图，若从顶点V。出发，按广度优先进行遍历，则可能得到的一种顶点序列为 ( ) 。在有序表2 ， 4， 7， 14， 34， 43， 47， 64， 75， 80， 90， 97， 120) 中，用折半查找法查找值80时，经 ( ) 次比较后查找成功

17、。 TOC o 1-5 h z A4B2C3D5排序算法中，从未排序序列中依次取出元素与已排序序列 （ 初始为空 ） 中的元素进行比较（ 要求比较次数尽量少） ，然后将其放入已排序序列的正确位置的方法是（ ）。A 冒泡B 直接插入C 折半插人D 选择排序 排序方法中， 从尚未排序序列中挑选元素， 并将其依次放入已排序序列 （ 初始为空 ） 的一端的方法，称为 （ ） 排序。A 归并 B 插入C 快速 D 选择二、填空题 （ 每小题 2 分。共 24 分 ）-结构中的数据元素存在多对多的关系称为一一结构。. 要求在 n 个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法

18、的时间复杂度分别为 和设有一个头指针为head的单向循环链表，p指向链表中的结点，若pnext=,则P所指结点为尾结点。向一个栈顶指针为h的链栈中插入一个 s所指结点时，可执行snext=h;和在一个链队中，设 f和r分别为队头和队尾指针，则插入s所指结点的操作为-和 r=s ； （结点的指针域为next）.设有n阶对称矩阵A,用数组s进行压缩存储，当inext=NULL；head=(1) ；2) ；for(i=1 ； idata=i ；p-next=NULL ；elsep-next2(4)；q 一 next2(5) ；return(head) ；2 以下程序是后序遍历二叉树的递归算法的程序，

19、完成程序中空格部分( 树结构中，左、右指针域分别为 left 和 right ，数据域 data 为字符型； BT 指向根结点 ) 。void Postorder(struct BTreeNode*BT)if(BT!=NULL) TOC o 1-5 h z ； ； ；试题答案及评分标准 一、单项选择题 ( 每小题 2 分，共 30 分)1C 2A 3 C 4C 5 C6 B 7 A 8 A 9 A l0 A11 D l2 C l3 A l4 C l5 D TOC o 1-5 h z 二、填空题 ( 每小题 2 分。共 24 分)- 图状 ( 网状 ). n 1, 0(n)headH=s； r

20、一 next=S ；.i(i 1)/2+j2i 和2i+1n中序 abdefeg不正确关键字相等的记录三、综合题 ( 每小题 10 分。共 30 分)1 (1) 初始序列 46， 79， 56， 38， 40， 84 TOC o 1-5 h z 40，79，56，38，回，8440 ，回， 56,38 ， 79， 8440，38，56，围，79，8440，38，回，56，79，8440，38，46，56，79，84，(2)2 (1) 原序列 16 15 20 53 64 715 16 20 53 7 64 n一 1 耥15 16 20 7 53 64 n j 次15 16 7 20 53 64

21、7 15 16 20 53 64平均查找长度一(1*1+2*2+3*3) 6 1463 (1) 不正确，二叉排序树要求其子树也是二又排序树。(2)后续遍历 5， 6， 4， 9， 8， 18， 20， 16， 7四、程序填空题 ( 每空 2 分。共 16 分) (1)P(2)q=P(3)(NODE*)malloc(sizeof(NODE)(4)q-next(5)p (1)Postorder(BT 一 left)(2)Postorder(BT 一 right)(3)printf(c”，BTdata)数据结构题库及答案三一、单项选择题。在括号内填写所选择的标号( 每小题 2 分。共 18 分)若需

22、要利用形参直接访问实参，则应把形参变量说明为 ( ) 参数。A.指针B.引用C 传值D 常值在二维数组中，每个数组元素同时处于( ) 个向量中。A O B 1C 2 D n.已知单链表A长度为m,单链表8长度为n,它们分别由表头指针所指向，若将B整体连接到A的 TOC o 1-5 h z 末尾，其时间复杂度应为 ( )。AO(1)BO(m)C.O(n)D.O(m十n)假定一个链式队列的队头和队尾指针分别为 front 和 rear ，则判断队空的条件为 ( ) A iront= =rear B front!=NULLC rear! = NULLD front= =NULL若让元素l ， 2 ，

23、 3 依次进栈，则出栈次序不可能出现( ) 种情况。 TOC o 1-5 h z A3，2，1B2，1，3C3，1 ，2D1，3，2在一棵高度为 5( 假定树根结点的高度为 0) 的完全二叉树中，所含结点个数至少等于A 16B 64C 31D 32向具有 n 个结点的二叉搜索树中插入一个结点的时间复杂度大致为 ( )A O(1) B O(1og2n)C O(n)D O(nlog 2n)8 具有 n 个顶点的有向图最多可包含有( ) 条有向边。A n 1B nC n(n 一 1) 2 D n(n 一 1)9 图的广度优先搜索类似于树的( ) 遍历。A.先根B.中根C.后根D.层次二、填空题。在横

24、线处填写合适的内容( 每小题 2 分，共 14 分)链表只适用于() 查找。设双向循环链表中每个结点的结构为 (data ， llink ， rlink) ，则结点 *P 的前驱结点的地址为()。在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有() 个结点。假定一棵树的广义表表示为a(b ， c ， d(e ， f) ， g(h) ，则结点 f 的层数为 () 。假定树根结点的层数为 0。从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的( ) 继续搜索。每次从第i 至第 n 个元素中顺序挑选出一个最小元素，把它交换到第 i 个位置，此种排序方法叫做 ()

25、 排序。快速排序在最坏情况下的时间复杂度为()。三、判断题，在每小题前面打对号表示正确或打叉号表示错误(每小题 2 分。共 14 分)()1数据的逻辑结构与数据元素本身的内容和形式无关。()2使用三元组表示稀疏矩阵中的非零元素能节省存储空间。( )3 在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历和按层遍历时具有相同的结果。( )4能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。( )5邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( )6 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表

26、个数有关，而且与每一个子表中的对象个数有关。( )7 向一棵 8树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少 1。四、运算题 ( 每小题 6 分。共 30 分 )假定一棵二叉树广义表表示为 a(b(c( ， g) ， d(e ， f) ，分别写出对它进行先序、中序和后序遍历的结果。先序：中序：后序：有 7 个带权结点，其权值分别为3， 7， 8， 2， 6， 10， 14，试以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度。带权路径长度：已知图 G=(V， E) ，其中V=a ， b， c， d， e ，E=， ， ， ， ， ， 在该图的邻接表表示中，每个顶

27、点单链表各有多少个边结点。顶点： a b c d e边结点数：.已知一个AOV网的顶点集V和边集G分别为：V=0， 1 ， 2， 3， 4， 5， 6， 7 ；E=， ， ， ， ， ， ， ， ；若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。拓扑序列：5 已知有一个数据表为 30 ， 16， 20， 15， 38， 12， 44， 53， 46， 18， 26， 86 ，给出进行归并排序16页的过程中每一趟排序后的数据表变化。(o)30 16 20 15 38 12 44 53 46 18 26

28、 86(2)五、算法分析题(每小题6分。共12分).该算法功能为：从表头指针为la的、按值从小到大排列的有序链表中删除所有值相同的多余元素,并释放被删结点的动态存储空间。阅读算法，在划有横线的上面填写合适的内容。void purge_linkst(ListNode * &la)ListNode * P , *q ;if(1a= =NULL)return ;q=1a; p=la -link;while(p)if(p -dataq -data)q=p ; p=p -link ; elseq -link ;delete(p);p= ；.已知二叉树中的结点类型BinTreeNode定义为：struct

29、 BinTreeNodeElemType data ; BinTreeNode*left , *right ; ;其中data为结点值域，left和right分别为指向左、布子女结点的指针域。下面函数的功能是从二 叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。阅读算法，在划有横线的上面 填写合适的内容。BinTreeNode*BTF(BinTreeNode*BT , ElemType x)if(BT=NULL)NULL ;elseif(BT - data= =x) ; elseBinTreeNode*t ;if(t BTF(BT left , x)return tif(t=

30、 )return t;return NULL ; 六、算法设计题(每小题6分，共12分) 1. Q是一个由其队尾指针和队列长度标识的循环队列，请写出插入一个元素的算法。 struct CyelieQueue/循环队列定义ElemType elemM ; / M为已定义过的整型常量int rear ;/rear指向队尾元素的后一个位置int length ;/length指示队列中元素个数；bool EnCQueue(CyclicQueue& Q , ElemType x);/Q是一个循环队列，若队列不满，则将x插入并返回true ；否则返回false。/在下面写出该函数的函数体2.已知二叉搜索

31、树中的结点类型BinTreeNode定义为：struct BinTreeNodeElemType data; BinTreeNode*left, *right;)其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树的根结点。试根据下面的函数声明编写一个递归算法，向BST树中插入值为item的结点，要求若树中不存在item结点则进行插入并返回l表示插入成功，若树中已存在item结点则不插入并返回。表示插入失败。int Insert(BinTreeNode*&BST , const ElemType&item);试题答案及评分标准一、单项选择题

32、。在括号内填写所选择的标号(每小题2分。共18分). B 2.C 3.B 4.D 5.C6. D 7.B 8.D 9.D18页二、填空题。在横线处填写合适内容( 每小题 2 分。共 14 分)1 顺序 2 p-llink 3 1 4 2 5 右子树6 直接选择7 0(n 2)三、判断题，在每小题前面打对号表示正确或打叉号表示错误( 每小题 2 分共 14 分 )1 对2对3对4错5 错 6 对 7 错四、运算题 ( 每小题 6 分共 30 分 ) TOC o 1-5 h z 1 先序：a， b， c ， g，d，e， f2 分中序：c ，g ，b，a，e，d，f2 分后序：g，c，b，e，f，

33、d，a2 分2带权路径长度：l31评分标准：每个数据对给l 分，全对给6 分。顶点： a b cd e边结点数： 11 21 2评分标准：若与答案完全相同得6 分，若仍为一种拓扑序列则得3 分，其他则酌情处理。其他则酌情处理。拓扑序列： 1 ， 3 ， 6， 0， 2 ， 5 ， 4， 75分步给分(0)30 16 20 15 38 12 44 53 46 18 26 86(1)16 3015 2012 3844 5318 4626 86 /l分(2)15 16 20 3012 38 44 5318 26 46 86 l 分(3)-r-1112 分(4)12 15 16 18 20 26 30

34、 38 44 46 53 86 /2分五、算法分析题【每小题 6 分。共 12 分 ) p -link 、 q -link. return BT、BTF(BT right , x)六、算法设计题 ( 每小题 6 分。共 12 分)评分标准：根据编程完整程度酌情给分。 bool EnCQueue(CyclicQueue&Q ， ElemType x) ；if(Q.1ength= =M)return false ； 1 分Q elemQ rear=x ； 2 分Q rear=(Q rear+1)%M ；/14 分Q 1ength+ ； 5 分return true ； 6 分 int Insert

35、(BinTreeNode*&BST ， const ElemType&item)if(BST= =NULL)BinTreeNode*p=new BinTreeNode ；p 一 data=item ；p 一 left=p 一 right=NULL ；BST=P：return l ；else if(item= =BST 一 data)return 0；else if(itemdata)return Insert(BST 一 left ， itern) ；elsereturn Insert(BST-right， item) ；说明：函数体中的三个else 保留字均可以被省略。数据结构题库及答案四

36、TOC o 1-5 h z 一、单项选择题(每小题 2 分，共30 分)同一种逻辑结构( ) 。A. 只能有唯一的存储结构B 可以有不同的存储结构C 只能表示某一种数据元素之间的关系 n 以上三种说法均不正确链表所具备的特点是( ) 。A 可以随机访问任一结点B 占用连续的存储空间C 插入删除元素的操作不需要移动元素结点D 可以通过下标对链表进行直接访问数据的物理结构( ) 。A与数据的逻辑结构无关B仅仅包括数据元素的表示C只包括数据元素间关系的表示n 包括数据元素的表示和关系的表示.线性结构中数据元素的位置之间存在（）的关系。A-对一B 一对多C多对多D.每一个元素都有一个直接前驱和一个直接

37、后继.设有一个10阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B中（数组下标从1开始），则矩阵中元素氏，。在一维数组B中的下标是.（）。A . 33 B . 32C . 85 D . 41 TOC o 1-5 h z .在一个无向图中，所有顶点的度数之和等于边数的（）倍。A3 & 2.5C 1.5 D . 2二、填空题（每小题 2分，共24分）. 栈和队列的操作特点分别是 和 一。.结构中的数据元素存在多对多的关系称为- 结构。.根据数据元素间关系的不同特性，通常可分为集合、线性、四类基本结构。.要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则

38、比较的 次数和算法的时间复杂度分别为 和 一。.在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行 和= 的操作。.在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、-。.-棵二叉树中顺序编号为 i的结点，若它存在左、右孩子，则左右孩子的编号分别为.向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行-;和。.在一个链队中，设f和r分别为队头和队尾指针，则插入 s所指结点白操作为-和r=s；（结点的指针域为next）。.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 个结点。（根所在结点为第. 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该

39、元素的 、 和非零元素值三项信息。. 在对一组记录 （55 ， 39， 97， 22， 16， 73， 65， 47， 88） 进行直接插入排序时，当把第7 个记录 65插入到有序表时，为寻找插入位置需比较一次。三、综合题（每小题 10 分，共 30 分） （1） 以 2 ， 3， 4， 7， 8 ， 9 作为叶结点的权，构造一棵哈夫曼树（要求每个结点的左子树根结点的权小于等于右子树根结点的权） ，给出相应权重值叶结点的哈夫曼编码。（2）- 棵哈夫曼树有n 个叶结点，它一共有多少个结点？简述理由。一组记录的关键字序列为 （46 ， 79， 56 ， 38， 40， 84）利用快速排序的方法，给

40、出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列） 。对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。30 设查找表为 （50 ， 60， 75， 85， 96， 98， 105， 110， 120， 130）说出进行折半查找成功查找到元素120 需要进行多少次元素间的比较？为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？画出对上述有序表进行折半查找所对应的判定树（要求以数据元素作为树结点） 。四、程序填空题（每空2 分，共 16 分）试题答案及评分标准一、单项选择题（每小题 2 分，共 30 分） TOC o 1-5 h z 1B

41、2 C 3D4 A5 D6C7 B 8C9 A10 C11 A 12B13C14A15 D二、填空题（每题 2 分其 24 分】数据结构题库及答案五一、单项选择题（每小题 2 分，共 30 分）在 C 语言中，顺序存储长度为 3 的字符串，需要占用 （ ） 个字节。 TOC o 1-5 h z A4B3C 6D12。串函数 StrCat（a ， b） 的功能是进行串 （ ）。A比较B复制C 。赋值 D 连接 - 棵有 n 个结点采用链式存储的二叉树中，共有( ) 个指针域为空。 TOC o 1-5 h z An+lBnCn-lDn-2设一棵哈夫曼树共有n 个非叶结点，则该树有( ) 个叶结点。

42、A n B n+lC n-l D 2n从一个栈顶指针为 top 的链栈中删除一个结点时，用变量x 保存被删结点的值，则执行( )A. x=top-data;top=top-next B.x=top-dataC. top= top-next; x=top-data D.top=top-next;x=data一棵完全二叉树共有5 层，且第 5 层上有六个结点，该树共有( ) 个结点。A30B20C21D23在一个无向图中，所有顶点的度数之和等于边数的 ( ) 倍。A.。上；B . 3C 1.5 D 2.已知如图1所示的一个图，若从顶点V,出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为(

43、 )。已知如图2 所示的一个图，若从顶点 a 出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。abcedfabcefdaebcfdacfdeb对二叉排序树进行( ) 遍历，可以使遍历所得到的序列是有序序列。A 按层次B 后序C 中序 D 前序80在有序表(2 ， 4， 7， 14， 34， 43， 47 ， 64， 75， 80， 90， 97， 120) 中，用折半查找法查找值时，经 ( ) 次比较后查找成功。A 4 B 2aC3 D5有一个长度为 9 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为 ( ) 。A 25/10 B 25/9C 20

44、/9 D 17/9排序算法中，从未排序序列中依次取出元素与已排序序殂（初始为空）中的元素进行比较（要求比较次数尽量少） ，然后将其放入已排序序列的正确位置的方法是（ ）。A 冒泡B 。直接插入C 折半插入D 选择排序一组记录的关键字序列为 （46 ， 79， 56 ， 38， 40， 84） ，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为 （ ）。A40,38946,79956,84B40,38946,56,79,84C40， 38,46,84,56,79D38， 40,46956,79,84排序方法中，从尚未排序序列中挑选元素，并将其依次放人已排序序列（初始为空）的一端的方法

45、，称为 （ ） 排序。A 归并B 插入C 快速D 选择二、填空题（每小题 2 分。共 24 分）在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是 、 、右指针。- 棵二叉树中顺序编号为 i 的结点，若它存在左、右孩子，则左、右孩子编号分别为串的两种最基本的存储方式是一 和 一。- 棵有 2n-l 个结点的二叉树，其每一个非叶结点的度数都为2 ，则该树共有个叶结点。对于一棵具有n 个结点的二叉树，其相应的链式存储结构中共有个指针域为空。 遍历二叉排序树可得到一个有序序列。22如图3所示的二叉树，其后序遍历序列为%图323 如图 4所示的二叉树，其先序遍历序列为妒图4图的深度优先搜索和广

46、度优先搜索序列不一定是唯一的。 此断言是一的。 (回答正确或不正确)二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是的。 (回答正确或不正确)对记录序列排序是指按记录的某个关键字排序，记录序列按 排序结果是唯一的。按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题(每小题 10 分。共 30 分)设查找表为 (16 ， 15， 20， 53， 64， 7) ，用冒泡法对该表进行排序(要求升序排列) ，写出每一趟的排序过程，通常对n 个元素进行冒泡排序要进行多少趟冒泡？第 j 趟要进行多少

47、次元素间的比较？在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。 (要求以数据元素作为树结点) 。29 (1) 设有查找表5 ， 14， 2， 6， 18， 7， 4， 16 ， 3) ，依次取表中数据，构造一棵二叉排序树。说明如何由序列的二叉排序树得到相应序列的排序结果。30 (1) 对给定权值2 ， 1， 3， 3 ， 4， 5，构造哈夫曼树(要求每个结点的左子树根结点的权小于等于右子树根结点的权) 。给出各权值的哈夫曼编码。四、程序填空题【每空2 分。共 16 分)以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右指针域分别为 1eft 和 ri

48、ght ，数据域 data 为字符型， BT 指向根结点) 。voidPostorder( structBTreeNode* BT)if(BT! =NULL)试题答案及评分标准一、单项选择题(每小题 2 分，共 30 分)1 A 2 D 3 A 4 B5.A6 C 7 D 8 A 9 B10.C11 B 12 B 13 C 14 B15.D二、填空题(每题 2 分，共 24 分)值域 左指针 右指针2i 2i+l顺序存储 链式存储/ , 一。 nr磷 n+1-中序 gdbeihfca。掣 3 abdefcg正确不正确主关键字关键字相等的记录数据结构题库及答案六一、单项选择题(每小题 2 分，共

49、 30 分)在数据结构和算法中，与所使用的计算机有关的是( )。A 数据元数间的抽象关系 B 数据的存储结构C 算法的时间复杂度D 数据的逻辑结构对顺序表，以下叙述中正确的是( ) 。A 用一组地址连续的存储单元依次存放线性表的数据元素B 各个数据元素的首地址是连续的C 数据元素不能随机访问D 插入操作不需要移动元素设有一个长度为 25 的顺序表，要删除第10 个元素(下标从1 开始) ，需移动元素的个数为 ( ) 。A 9 B 10C 15 D 16.设单向链表中，指针 p指向结点A,若要删除A的直接后继，则所需修改指针的操作为 TOC o 1-5 h z ( )。13. 已知如图 1 所示

50、的一个图，若从顶点 a 出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为() 。abedfc BacfebdC aebcfdDaedfbc14 一组记录的关键字序列为 (46,20,30,79,56,38,40,84,90il10) ，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为 ( )。A. 20,30,40,38,46,79,56,84,90 ,10040,20,30,38,46,56,79,84,90 ,11030,20 ,40,38,46,84,56,79,90 ,10020,30 38,40 i46,56 ,79 ,84 ,90 ,10015. 一组记录的关键字序列为(75,63,95