大数据结构试的题目及问题详解计算机数据结构与算法_计算机-数据结构与算法.pdf

《大数据结构试的题目及问题详解计算机数据结构与算法_计算机-数据结构与算法.pdf》由会员分享，可在线阅读，更多相关《大数据结构试的题目及问题详解计算机数据结构与算法_计算机-数据结构与算法.pdf（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构试题 单选题（每题 2 分，共 20 分）1.1.对一个算法的评价，不包括如下（B）方面的内容。A.健壮性和可读性 _B.并行性 C.正确性 D.时空复杂度 2.2.在带有头结点的单链表 HL 中，要向表头插入一个由指针 p 指向的结点，则执行（A）。A.p-n ext=HL-n ext;HL-n ext=p;B.p-n ext=HL;HL=p;C.p-next=HL;p=HL;D.HL=p;p-next=HL;3.3.对线性表，在下列哪种情况下应当采用链表表示？（B）A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数

2、不变 4.4.一个栈的输入序列为 1 23，贝 U 下列序列中不可能是栈的输 出序列的是（C）A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 5.5.AOV 网是一-种（D）。A .有向图 B.无向图 C.无向无环图 D.有向无环图 6.6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。A.低于链接法处理冲突 B.高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D）参数。A.值 B.函数 C.指针 D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的 结点都具有相同的（A）。A

3、.行号 B列号 C.元素值 D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（D）。A.O（log 2n）B.0（nlog 2n）C.0（n）D.O（n2）10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为（C）。A.O（n）B.O（1）C.O（log 2n）D.O（n 2）二、运算题（每题 6 分，共 24 分）1.1.数据结构是指数据及其相互之间的 对应关系（联系）。当结点之间存在 M 对 N（M N）的联系时，称这种结构为 图（或图结构）。2.2.队列的插入操作是在队列的 队尾 进行，删除操作是在队列的 对头_ 进行。3.3.当用长度为 N 的数组顺序存储一个栈时，

4、假定用 top=N 表示栈空，则表示栈满的条件是_top=0_。4.4.对于一个长度为 n 的单链存储的线性表，在表头插入元素的时间复 杂度为_0(1)_，在表尾插入兀素的时间复杂度为 0(n)o 5.5.设 W 为一个二维数组，其每个数据元素占用 4 个字节，行下标 i从 0 到 7，列下标 j从 0 到 3，则二维数组 W 的数据元素共占用128个字节。W 中第 6 行的元素和第 4 列的元素共占用 44 个字节。若按行顺序存放 二维数组 W 其起始地址为 100,则二维数组元素 W6,3 的起始地址为 108 o 6.6.广义表 A=(a,(a,b),(a,b),c),则它的深度为 3，

5、它的长度为 3 o 7.7.二叉树是指度为 2 的有序_树。一棵结点数为 N 的二叉树，其所有结 点的度的总和是 n-1 o 8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个有序序列 _0对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是 该算术表达式的后缀表达式_0 9.9.对于一棵具有 n 个结点的二叉树，用二叉链表存储时，其指针总数为 2n 个，其中 n-1 个用于指向孩子,n+1 个指针是空闲的。10.10.若对一棵完全二叉树从 0 开始进行结点的编号，并按此编号把它顺序存 储到一维数组 A 中，即编号为 0 的结点存储到 A0中。其余类推，贝 U A i 元素

6、的左孩子元素为 2i+1,右孩子元素为 2i+2，双亲元素为 _(i-1)/2_ o 11.11.在线性表的散列存储中，处理冲突的常用方法有_开放地址法_和_链接 法一两种。12.12.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用 _快速排序；当待排序的记录数较大，存储空间允许且要求排序是稳定 时，宜采用归并排序。三、运算题(每题 6 分，共 24 分)1.1.已知一个 6 5 稀疏矩阵如下所示,0 0 0 0 1 0 0 0 0 0 0-100 0 0 0 00-2 5 0 0 0 0 0 0 7 0 0 一 度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对

7、线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当试：(1)写出它的三元组线性表；(2)给出三元组线性表的顺

8、序存储表示。2.2.设有一个输入数据的序列是 46,25,78,62,12,80,试画出从 度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之

9、间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当空树起，逐个输入各个数据而生成的二叉搜索树。3.3.对于图 6 所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的 边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点出发进行广度优先搜索所得到的广度优先生成树；4.4.已知一个图的顶点集 V 和边集 E 分别为：V=1,2,3,4,5,6,7;E=,v3,2,v3,6,v4,3,;若存储它采用邻接表，并且每个顶 点邻接表中的边结点都是按照终点序 号从小到大的次序链接的，按主教

10、材 中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列 四、阅读算法(每题 7 分，共 14 分)1.1.int Prime(int n)int i=1;int x=(i nt)sqrt(n);while(+ix)retur n 1;else return 0;(1)(1)指出该算法的功能；(2)(2)该算法的时间复杂度是多少?2.2.写出下述算法的功能：void AJ(adjlist GL,i nt i,i nt n)Queue Q;Ini tQueue(Q);coutvvivv;visitedi=true;Qin sert(Q,i);while(!QueueEmpty(Q)int k

11、=QDelete(Q);edge no de*p=GLk;while(p!=NULL)int j=p-adjvex;if(!visitedj)度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分

12、数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当查找失败，返回-1 coutvvjvv;visitedj=true;QI nsert(Qj);p=p-n ext;五、算法填空(共 8 分)如下为二分查找的非递归算法，试将其填写完整。Int Binsch(ElemType A,int n,KeyType K)int low=0;int high=n-1;while(low=high)int mid=_；if(K=Amid.key)return mid;/查找成功，返回元素的下标 else if(K

13、mid.key);/在左子表 上继续查找 else ;/在右子 表上继续查找 return-1;/六、编写算法(共 8 分)HL 是单链表的头指针，试写出删除头结点的算法 ElemType DeleFro nt(LNode*&HL)参考答案 度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函

14、数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当low=mid+1 三、运算题（每题 6 分，共 24 分）1.1.（1）(1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)(3 分)（2）三兀组线性表的顺序存储表示如图 7 示。6 5 5 2.2.如图 8 所示。1 5 1 3.3.DFS 3 2-1 BFS 4 5-2 4.4.拓朴排序为：4 3 6 5 7 2

15、1 5 1 5 四、阅读算法（每题 7 分，共 14 分）6 3 7（2）0（i n）2.2.功能为：从初始点 Vi出发广度优先搜索由邻接表 GL 所表示的图 五、算法填空（8 分）(low+high)/2 high=mid-1 六、编写算法(8 分)ElemType DeleFro nt(LNode*&HL)if(HL=NULL)cerr 空表 next;ElemType temp=p-data;delete p;return temp;课程测试试题（1 卷）、单选题（每题 2 分，共 20 分）1.1.栈和队列的共同特点是（A）。A.只允许在端点处插入和删除元素 (b)(c)(d)g Cf

16、)图 8 1.1.（1）判断 n 是否是素数（或质数）度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构

17、队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当692 D.696 无序数据元素 D.元素之间无联系的数据 B.都是先进后出 C.都是先进先出 D.没有共同点 2.2.用链接方式存储的队列，在进行插入运算时(D).A.仅修改头指针 B.头、尾指针都要修改 C.仅修改尾指针 D.头、尾指针可能都要修改 3.3.以下数据结构中哪一个是非线性结构？(D)A.队列 B.栈 C.线性表 D.二叉树 4.4.设有一个二维数组 Am【n，假设 A00存放位置在 644 佝，A22存放位置在 676(io)，每个元素占一个空间，问 A33(10)存放在什 么位置？脚注(io)表示用 10 进制表示

18、。(C)A.688 B.678 C 5.5.树最适合用来表示(C)n ext)q=L；L=L next;p=L;51:while(p next)p=p next;52:p next=q;q next=NULL;return L；请回答下列问题：(1)说明语句 S1 的功能；(2)说明语句组 S2 的功能；(3)设链表表示的线性表为(a1,a2,an),写出算法执行后的返回值 所表示的线性表。2.2.void ABC(BTNode*BT)if BT ABC(BT-left);ABC(BT-right);coutdatadata)item=BST-data;查找成功 return _;else i

19、f(itemdata)return Find _,item);else return Find _,item);度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的

20、对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当三、运算题（每题 1.1.参考答案 6 分，共 24 分）线性表为：2.邻接矩阵:2.邻接表如图 11 所示:(78,50,0 1 1 卫 1 0 1 0 1 1 1 0 1 1 40,1 0 1 0 1 60，34，90)01 1 1 1 0 3.3.(1,2)3,4.4./if 六、编写算法（共 8 分）统计出单链表 HL 中结点的值等于给定值 X 的结点数 int Cou ntX（LNode*HL,ElemType x）图 11 用克鲁斯卡尔算法得到的最小生成树为:（1,

21、3）5,（1,4）8,见图 12 图 12 四、阅读算法（每题 7 分，共 14 分）(4,6)4,(2,5)10,度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之

22、间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当1.1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点 3）返回的线性表为（a2,a3,an,aj 2.2.递归地后序遍历链式存储的二叉树。五、算法填空（每空 2 分，共 8 分）true BST-left BST-right 编写算法（8 分）int Cou ntX(LNode*HL,ElemType x)int i=0;LNode*p=HL;/i 为计数器 while(p!=NULL)if(P-data=x)i+;p=p-n ext;/whil

23、e,出循环时 i中的值即为 x 结点个数 return i;/Cou ntX 课程测试试题（2 卷）、单选题（每小题 2 分，共 8 分）1、1、在一个长度为 n 的顺序线性表中顺序查找值为 x 的元素时，查找成功时的 平均查找长度（即 x 与元素的平均比较次数，假定查找每个元素的概率 都相等）为（C）o A n B n/2 C（n+1）/2 D（n-1）/2 2、2、在一个单链表中，若 q 所指结点是 p 所指结点的前驱结点，若在 q 与 p 之间 插入一个 s 所指的结点，则执行（D）o A s f link=p f link;p link=s;B p f link=s;s f lin k

24、=q;C p f link=s f link;s f link=p;D q f link=s;s f link=p;3、3、栈的插入和删除操作在（A）进行。A 栈顶 B 栈底 C 任意位置 D 指定位置 4、4、由权值分别为 11,8,6,2,5 的叶子结点生成一棵哈夫曼 树，它的带权路径长度为（B）A 24 B 71 C 48 D 53 二、填空题（每空 1 分，共 32 分）5、1、数据的逻辑结构被分为集合、_线性 _、树 _ 和 _ 图 _ 四种。6、2、一种抽象数据类型包括_数据描述 _ 和一操作声名两个部分。度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列

25、哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当7、3、在下面的数组 a 中链接存储着一个线性表，表头指针为 ao.n

26、ext，则该线性表为 _（38,56，25,60,42，74）。&4、在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中，判 断链表为空的条件分别为 Hn ext=NULL 和 HL=Hn ext。9、5、用具有 n 个元素的一维数组存储一个循环队列，则其队首指针总是指 向队首元素的 前一个位置，该循环队列的最大长度为 n-1 0 10、6、当堆栈采用顺序存储结构时，栈顶元素的值可用 S.stack S.top 表示；当堆栈采用链接存储结构时，栈顶元素的值可用_H4data _ 表示。11、7、一棵高度为 5 的二叉树中最少含有 5 个结点，最多含 31 个结 点。12、&在图的邻接

27、表中，每个结点被称为 _边结点，通常它包含三个 域：一是一邻接点域_；二是权域；三是一链域_ 0 13、9、在一个索引文件的索引表中，每个索引项包含对应记录的 一索引 值域和开始位置域两项数据。14、10、假定一棵树的广义表表示为 A(B(C,D(E,F，Q，H(l，J),贝 U 树中所含的结点数为 10 个，树的深度 为 3,树的度为_3_,结点 H 的双亲结点为 B,孩子结点为 I和 J 0 15、11、在堆排序的过程中，对任一分支结点 进行筛运算的时间复杂度为_O(log 2n)整个堆排序过程的时间复杂度 为_ 0(nlog?n)_ o 16、12、在对 m 阶的 Bj 树插入元素的过程

28、中，每向一个结点插入一个索引项(叶子结点中的索引项为关键字和空指针)后，若该结点的索引项数等于_ m _ 个，则必须把它分裂为_ m-1_ _ 个 结点。三、运算题(每小题 6 分，共 24 分)17、1、已知一组记录的排序码为(46,79,56,38,40,80,95，24)，写出对其进行快速排序的每一次划分结果。18、2、一个线性表为 B=(12,23,45,57,20,03,78,31,15,36),设散列表为 HT0.12，散列函数为 H(key)=key%13 并用线性探查 法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找 长度。19、3、已知一棵二叉树的前序遍历的结果

29、序列是 ABECKFGH,中序遍历 60 56 42 38 74 25 4 3 7 6 2 0 1 a 0 1 2 3 4 5 6 7 8 data n ext 度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致

30、为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当-1，请 的结果是 EBCDAFHIGJ 试写出这棵二叉树的后序遍历结果 20、4、已知一个图的顶点集 V 各边集 G 如下：V=0,1,2,3,4,5,6,7,8,9；E=（0,1）,（0,4）,（1,2）,（1,7）,（2,8）,（3,4）,（3,8）,（5,6）,（5,8）,（5,9）,（6,7）,（7,8）,（8,9）当它用邻接矩阵表示和邻接表表示时，分别写出从顶点 V0出发按深度优先 搜索遍历得到的顶点序列和按广度优先

31、搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。图 深度优先序列 广度优先序列 邻接矩阵表示时 邻接表表示时 四、阅读算法，回答问题(每小题 8 分，共 16 分)1、假定从键盘上输入一批整数,依次为：78 63 45 30 91 34 写出输出结果。#in elude#in elude con sst int staekmaxsize=30;typedef int elemtype;struct stack elemtype stack stackmaxsize;int top;；#include“stack.h”Void mai n()stack a;i

32、ni tstack(a);int x;cin x;while(x!=-1)push(a,x);cin x;while(!stackempty(a)cout pop(a)cout e ndl;度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查

33、找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当 该算法的输出结果为：2、阅读以下二叉树操作算法，指出该算法的功能。Template void Bin Tree :unknown(Bin TreeNode*t)Bin TreeNode*p=t,*temp;if(p!=NULL)temp=p f leftchild;p f leftchild=p f rightchild;p f rightchild=temp;unknown f leftchild

34、);undnown(p f rightchild);该算法的功能是：_ 五、算法填空，在画有横线的地方填写合适的内容（10 分）对顺序存储的有序表进行二分查找的递归算法。int Bin sch(ElemType A,i nt low,int high,KeyType K)if(low=high)int mid=1 if(K=A mid.key)return mid;else if(K next next。18.19.20.24.在有序表 行的关键字比较次数为 2。25.多重表文件和倒排文件都归属于多关键字文件。三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)26.画出下列广义表的

35、共享结构图形表示 P=(z),(x,y),(x,y),x),(z)27.请画出与下列二叉树对应的森林。00011 28.已知一个无向图的顶点集为a,b,c,d,e,其邻接矩阵如下所示 a J0110 一 b(1)画出该图的图形；c(2)根据邻接矩阵从顶点 a 出发进行深度优先遍历和广度优先遍历,d 写出相应的遍历序列。e 度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突

36、与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当29.已知一个散列表如下图所 示:35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为 h(key)=key%13,处理冲突的方法为双重散列法，探查序列为:h i=(h(key)+i*h1(key)%m i=0,1,m-1

37、 其中 度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队

38、列的对头进行当1 当 S s2 comstr(s 1,请在空白处填入适当的内容。h1(key)=key%11+1 回答下列问题：(1)对表中关键字 35,20,33 和 48 进行查找时，所需进行的比较次数各 为多少？(2)该散列表在等概率查找时查找成功的平均查找长度为多少?四、算法阅读题(本大题共 4 小题，每小题:s5 分，共 20 分)30 下列算法的功能是比较两个链串的大小，其返回值为：s 2)=L.in t comstr(Li nkStri ng s1,Li nkStri ng s2)/s1 和 s2 为两个链串的头指针 while(s1&s2)if(s1 datedate)retu

39、r n 1；if(s1 dates2 date)retur n1；if()retur n 1；if()return1；31 阅读下面的算法 Lin kList myno te(L in kList L)/L 是不带头结点的单链表的头指针 if(L&L-n ext)q=L；L=L next；p=L；51:while(p next)p=p next；52:p next=q；q next=NULL；return L；请回答下列问题：(1)说明语句 S1 的功能；(2)说明语句组 S2 的功能；(3)设链表表示的线性表为(a1,a2,an),写出算法执行后的返回值 所表示的线性表。32 假设两个队列共

40、享一个循环向量空间(参见右 A3 下图，度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作

41、是在队列的队尾进行删除操作是在队列的对头进行当洪还修亠fronts 其类型 Queue2 定义如下：typedef struct DateType dataMaxSize;int fron t2,rear2；Queue2；对于 i=0 或 1,fronti 和 reari分别为第 i个队列的头指针和尾指针。请对以下算法填空，实现第 i个队列的入队操作。int En Queue(Queue2*Q,i nt i,DateType x)/若第 i个队列不满，则元素 x 入队列，并返回 1;否则返回 0 if(i1)return 0；if(Q reari=Q fron t return0；Q data

42、=x；Q reari=;returnl；33 已知二叉树的存储结构为二叉链表，阅读下面算法。typedef struct node DateType data；Struct node*n ext；ListNode；typedef ListNode*Lin kList；Lin kList Leafhead=NULL；Void Ino rder(Bi nTree T)Lin kList s；If(T)In order(T lchild)；If(!T lchild)&(!T rchild)s=(ListNode*)malloc(sizeof(ListNode)；s data=T data；s nex

43、t=Leafhead；Leafhead=s；度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入

44、操作是在队列的队尾进行删除操作是在队列的对头进行当In order(T rchild)；对于如下所示的二叉树 度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对

45、应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当图 1 27.else return i-1；(1)画出执行上述算法后所建立的结构;(2)说明该算法的功能。五、算法设计题(本题共 10 分)34.阅读下列函数 arrange()int arran ge(i nt a,i nt 1,i nt h,i nt x)/1 和 h 分别为数据区的下界和上界 int i,j,t;i=1；j=h；while(ij)while(i=x)j-；while(i=x)i+；if(ij)t=aj；aj=ai；ai=t；if(ainext s2=s2

46、next s2(或 s2!=NULL 或 s2&!s1)s1(或 s1!=NULL 或 s1&!s2)return 0 31.(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部，作为新的尾结点(3)返回的线性表为(a2,a3,an,aj 32.(i+1)%2(或 1 i)Q reari (Q reari+)%Maxsize 33.(1)Leafhead(2)中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以 Leafhead为头指针的逆序单链表(或按二叉树中叶子结点数据自右至 左链接成一个链表)五、算法设计题(本题共 10 分)34.(1)该函数的功能是：调整整数数组 a中的元素并

47、返回分界值 i，使所 有vx的元素均落在 a1.i 上，使所有x 的元素均落在 ai+1.h 上。(2)int f(int b,int n)或 int f(int b,int n)int p,q;int p,q；p=arrange(b,0,n 1,0)；p=arrange(b,0,n 1,1)；度在带有头结点的单链表中要向表头插入一个由指针指向的结点则执行对线性表在下列哪种情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间一个栈的输入序列为开放定址法处理散列表的冲突时其平均查找长度低于链法处理冲突高于链法处理冲突与链法处理冲突相同高于二分查

48、找若需要利用形参直访问实参时应将形参变量说明为参数值函数指针引用在稀疏矩阵的带行指针向量的链存储中每树中查找一个元素时其时间复杂度大致为二运算题每题分共分数据结构是指数据及其相互之间的对应关系联系当结点之间存在对的联系时称这种结构为图或图结构队列的插入操作是在队列的队尾进行删除操作是在队列的对头进行当1,1)；q=arrange(b,O,p,O)return p q；q=arran ge(b,p+1,n return q p；课程测试试题(3 卷)、选择题(20 分)1 组成数据的基本单位是(C)。(A)数据项(B)数据类型(C)数据元素(D)数据变量 2设数据结构 A=(D,R),其中 D=

49、1,2,3,4,R=r,r=,，则数据结构 A 是(C)。(A)线性结构(B)树型结构(C)图型结构(D)集合 3 数组的逻辑结构不同于下列(D)的逻辑结构。(A)线性表(B)栈(C)队列(D)树 4.二叉树中第 i(i 1)层上的结点数最多有(C)个。(A)2i(B)2 1(C)2 i-1(D)2i-1 5.设指针变量 p 指向单链表结点 A,则删除结点 A 的后继结点 B 需要的操作为(A)。(A)p-n ext=p-n ext-n ext (C)p=p-n ext-n ext (B)p=p-n ext (D)p-n ext=p 6.设栈 S 和队列 Q 的初始状态为空，元素 E1、E2、

50、E3 E4 E5 和 E6 依次通过 栈 S,一个元素出栈后即进入队列 Q 若 6 个元素出列的顺序为 E2、E4 E3、E6 E5 和 E1，则栈 S 的容量至少应该是(C)。(A)6(B)4(C)3(D)2 7.将 10 阶对称矩阵压缩存储到一维数组 A 中，贝擞组 A 的长度最少为(C)(A)100(B)40(C)55(D)80 8.设结点A有3 个兄弟结点且结点B 为结点A的双亲结点，则结点B 的度数数 为(B)。(A)3(B)4(C)5(D)1 9.根据二叉树的定义可知二叉树共有(B)种不同的形态。(A)4(B)5(C)6(D)7 10.10.设有以下四种排序方法，贝 9(B)的空间