数据结构导论02142

第 1 页 浙江省 2001 年 10 月自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题 (在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。每小题 1 分，共14 分 ) ) 输出关系 用 ( )比较合适。 误的为 ( ) 个结点只有一个链域 空的判断条件是 ( ) A. B. . D. ) 有 3 个结点的二叉树有 ( )种。 中序遍历的序列为 ( ) A.a,b,d,g,c,e,f,h B.d,g,b,a,e,c,h,f C.g,d,b,e,h,f,c,a D.a,b,c,d,e,f,g,h 的二叉树至多有 ( )个结点。 n 个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为 ( ) 数 n 个顶点的无向图中，要连通全部顶点至少需要 ( )条边。 ) 为散列函数不是一对一的关系，所以选择好的 ( )方法是散列文件的关键。 ( ) 000 个无序的元素，希望用最快的速度挑选出其中前 50 个最大的元素，最好选用 ( )法。 二、判断题 (判断下列各题，正确的在题干后面括号内打“”，错误的打“”。每小题 2 分，共 20 分 ) ( ) 个结点都有一个直接前驱和 一个直接后继。 ( ) ( ) a b c g e h 第 2 页 ( ) ( ) ( ) ( ) 须复制整个文件。 ( ) 该方法没有实际的应用价值。 ( ) n 个记录的集合进行冒泡排序 ，在最坏情况下所需要的时间是 0( ) 三、填空题 (每小题 2 分，共 30 分 ) _和 _。 a= b= c= - ,则 a 与 c 连接然后与 b 连接的结果为： _。 _；单链表的首结点指的是 _。 a、 b、 c、 d，则队列的输出序列为 _。 _和 _。 个结点的完全二叉树的深度为 _。 _、 _和层次遍历。 中，若 A i,j等于 1，则 A j,i等于 _。 要考虑的两个主要问题是：构造 _和解决 _。 (1)_； (2)_。 干的记录组成一个存储单位，称作 _。 而言，按用户的观点所确定的基本存储单元称为 _。按外设的观点所确定的基本存储单元称为_。 _存取、 _存取和按关键字存取。 _排序。 _。 四、应用题 (每小题 6 分，共 18 分 ) 1. 假定在学生的档案中含有：姓名、学号、年龄、性别。如采用线性表作为数据结构来实现档案管理问题，分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义。 使用五个字符： a、 b、 c、 d、 e,它们的出现频率依次为 8、 14、 10、 4、 18，请构造相应的哈夫曼树 (左子树根结点的权小于等于右子树根结点的权 )，求出每个字符的哈夫曼编码。 98,65,38,40,12,51,100,77,26,88,给出对其进行归并排序 (升序 )的每一趟的结果。 五、设计题 (每小题 6 分，共 18 分 ) 称为循环链队 )，该队列中只设一个队尾指 针 设队首指针。请编写向循环链队中插入一个元素 X 的过程。 写出连通图的深度优先搜索算法。 19,01,23,14,55,20,84,27,68,11,10,77,采用散列函数： H(3, 采用线性探测法解决冲突，试在 0 18 的散列地址空间中对该关键字序列构造散列表。 浙江省 2001 年 10 月自学考试 数据结构导论试题参考答案 课程代码： 02142 一、单项选择题 (每小题 1 分，共 14 分 ) 、判断题 (每小题 2 分，共 20 分 ) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 三、填空题 (每小题 2 分，共 30 分 ) 1.(1)数据表示 (2)数据处理。 2. 3.(1)在单链表第一个结点之前增设的一个类型相同的结点 (2)表结点中的第一个结点。 4. a、 b、 c、 d。 5.(1)顺序存储结构 (2)链表存储结构。 6. +1。 第 3 页 7.(1)先根遍历 (2)后根遍历。 9.(1)散列函数 (2)冲突。 10.(1)确定待查元素所在的块 (2)在块内查找待查的元素。 12.(1)逻辑 结构 (2)物理结构。 13.(1)顺序 (2)直接。 四、应用题 (每小题 6 分，共 18 分 ) =100; 顺序表的容量 档案数据类型 10 ;姓名 学号 性别 年龄 1. of 链接实现： 10 ;姓名 学号 性别 年龄 结点的后继指针 相应的哈夫曼编码为： a:001 b:10 c:01 d:000 e:11 画出正确的哈夫曼树给 4 分，写出相应哈夫曼编码给 2 分 3. 初始无序序列： 98 65 38 40 12 51 100 77 26 88 98 65 38 40 12 51 100 77 26 88 第一次归并： 65 98 38 40 12 51 77 100 26 88 第二次归并： 38 40 65 98 12 51 77 100 26 88 第三次归并： 12 38 40 51 65 77 98 100 26 88 第四次归并： 12 26 38 40 51 65 77 88 98 100 五、设计题 (每小题 6 分，共 18 分 ) x =x; 54 22 32 12 10 4 8 14 18 0 0 0 1 1 1 1 0 d a c b e 第 4 页 循环队列为空，新结点是队列的首结点 = 队列不空，将新结点插入在队列尾 =g: 从 发，深度优先遍历图 g = 标志 访问 p=g 找 第一个邻接点 if p ) g,p p =p 找 下一个邻接点 以邻接表为存储结构，连通图的深度优先搜索就是顺序查找链表。 H(19)=19 3=6 H(01)=01 3=1 H(23)=23 3=10 H(14)=14 3=1(冲突 ) H(14)=(1+1) 9=2 H(55)=55 3=3 H(20)=20 3=7 H(84)=84 3=6 (冲突 ) H(84)=(6+1) 9=7 (仍冲突 ) H(84)=(6+2) 9=8 H(27)=27 3=1 (冲突 ) H(27)=(1+1) 9=2 (冲突 ) H(27)=(1+2) 9=3 (仍冲突 ) H(27)=(1+3) 9=4 H(68)=68 3=3 (冲突 ) H(68)=(3+1) 9=4 (仍冲突 ) H(68)=(3+2) 9=5 H(11)=11 3=11 H(10)=10 3=10 (冲突 ) H(10)=(10+1) 9=11 (仍冲突 ) H(10)=(10+2) 9=12 H(77)=77 3=12 (冲突 ) H(77)=(12+1) 9=13 因 此，各关键字相应的地址分配如下： 1)=1 4)=2 5)=3 7)=4 8)=5 9)=6 第 5 页 0)=7 4)=8 3)=10 1)=11 0)=12 7)=13 其余 的地址中为空。 浙江省 2002 年 1 月自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题 (在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题 1 分，共 14 分 ) )。 p结点不是最后结点，在 p之后插入 s结点，则实行 ( )。 A. s p； p s; B. s p p s； C. s p p:=s; D. p s;s p; 00，每个元素的长度为 2，则第五个元素的地址是 ( )。 0.放其 元素值，已知其头尾指针分别是 当前队列中的元素个数是( )。 A.(m) m )。 n 的二叉树中所含叶子结点的个数最多为 ( )个。 )。 第 6 页 ( )不是完全二叉树。 )。 个结点的无向图，该图至少应 有 ( )条边才能确保是一个连通图。 求线性表必须 ( )。 结点按关键字有序排序 结点按关键字有序排序 )。 占用较多的存储空间 存取效率高 )。 47、 78、 61、 33、 39、 80)，则利用堆排序的方法建立的初始堆为 ( )。 47、 61、 33、 39、 80 78、 61、 33、 39、 47 78、 61、 47、 39、 33 61、 78、 39、 47、 33 二、判断题 (判断下列各小题，正确的在题后括号内打“ ”，错的打“ ”。每小题 2 分，共 20 分 ) 以在数据结构中二者是通用的。 ( ) ( ) ( ) ( ) 。 ( ) ( ) 于建立二叉排序树时插入结点的先后次序不同，所构成的二叉 排序树的形态及深度也不同，所以含有 n 个 结点的二叉排序树不唯一。 ( ) 须复制整个文件。 ( ) 直接选择排序是不稳定的。 ( ) n 个记录的集合进行冒泡排序，所需要的平均时间是 0(n)。 ( ) 三、填空题 (每小题 2 分，共 30 分 ) _、 _、 _和 _。 _。 3.设 单链表的头结点，则判断单链表为 空的条件是： _。 n 个单元的循环队列中，队满时共有 _个元素。 _的多个元素只分配一个存储空间， _不分配空间。 子链表表示法、 _和 _。 的完全二叉树至少有 _个结点，至多有 _个结点。 别为： _和 _。 点的平衡因子定义为该结点 _子树的高度减去该结点 _子树的高度。 _方式，又是一种 _方法。 录不按关键字顺序排列，因此对每个记录要建立一个索引项，这样的索引表称为_索引。 第 7 页 _、 _和更新记录三种操作。 盘存储器的优点是存取速度快，既适应于 _存取，又适应于 _存取。 _个记录的辅助空间。 初始数据基本正序，则选用 _；若初始数据基本反序，则选用 _。 四、应用题 (每小题 6 分，共 24 分 ) a= 1234+-*、 b= 1+2，请用串的各种基本运算将串 a 转换为串 b。规定：运算中不能引入新的字符串，所有的字符串只能从串 a 中取得。 画出能得到此中序遍历结果的二叉树的所有形态。 15,18,60,41,6,32,83,75,95。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。 五、设计题 (每小题 6 分，共 12 分 ) 1. 如下图所示，设有两个栈 亨同一数组存储空间 1.其中栈 栈底设在 1处，而栈 栈底设在 m处，请编写栈 进栈操作 i,x)和退栈操作 i)，其中 i=1、 2，分别表示栈 求：仅当整个空间 1.满时才产生上溢。 87, 25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 47，已知散列函数为 H(k)=k 3，采用拉链法处理冲突，设计出该开散列表的结构。 浙江省 2002 年 1 月自考 数据结构导论试题答案 课程代码： 02142 一、单项选择题 (每小题 1 分，共 14 分 ) 、判断题 (每小题 2 分，共 20 分 ) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 三、填空题 (每小题 2 分，共 30 分 ) 1.(1)正确性 (2)易读性 (3)强壮性 (4)高效率。 线性表也正确。 .(1)值相同 (2)零元素。 6.(1)孩子兄弟链表示法 (2)双亲表示法。 7.(1)2)2 8.(1)邻接矩阵 (2)邻接表。 9.(1)左 (2)右。 10.(1)存储 (2)查找。 12.(1)删除 (2)插入。 13.(1)顺序 (2)随机。 第 8 页 15.(1)插入排序 (2)选择排序。 四、应用题 (每小题 6 分，共 24 分 ) a,1,1),a,5,1); a,2,1),a,6,1); a,3,1),a,7,1); a,4,1); a1, a3, b=a6,2. 共有 5 种不同形态的二叉树，具体如下： 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 邻接表为： 初始序列： 15， 18， 60， 41， 6， 32， 83， 75， 95 第一趟： 15， 18， 41， 6， 32， 60， 75， 83， 95 第二趟： 15， 18， 6， 32， 41， 60， 75， 83， 95 第三趟： 15， 6， 18， 32， 41， 60， 75， 83， 95 第四趟： 6， 15， 18， 32， 41， 60， 75， 83， 95 第五趟： 6， 15， 18， 32， 41， 60， 75， 83， 95 在第五趟排序时已无元素交换，则排序结束。 五、设计题 (每小题 6 分，共 12 分 ) i, x: 进栈操作 if(判断是否出现上溢 发生上溢 )； i=1) 对栈 行进栈操作 =; :=x; 对栈 行进栈操作 9 页 =:=x； i) 退栈操作 i=1) 对栈 行退栈操作 ) 判断栈 否下溢 栈 现下溢 )； 栈 栈 ; 对栈 行退栈操作 if(m+1) 判断栈 否下溢 栈 现下溢 )； 栈 栈 ; ; 根据共享栈 1。 m的结构，设 栈 栈顶指针， 栈 栈顶指针。则当 时出现上溢，而当 时，栈 现下溢，当 m+1 时，栈 现下溢。 指针 全国 2003 年 10 月高等教育自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1下列说法正确的是（ ） A数据是数据元素的基本单位 B数据元素是数据项中不可分割的最小标识单位 C数据可由若干个数据元素构成 D数据项可由若干个数据元素构成 2数据结构的基本任务是（ ） A逻辑结构和存储结构的设计 B数据结构的运算实现 C数据结构的评价与选择 D数据结构的设计与实现 3在一个具有 n 个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ） A O（ 1） B O（ n） C O（ D O(4顺序存储的线性表（ a1, ,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ） A n B n/2 C n+1 D (n+1)/2 5下列 树 U，经剪技运算 U， x， 2）后为（ ） 第 10 页 6一棵有 16 结点的完全二叉树，对它按层编号，则对编号为 7 的结点 X，它的双亲结点及右孩子结点的编号分别为（ ） A 2， 14 B 2， 15 C 3， 14 D 3， 15 7设有一 5 阶上三角矩阵 A 1.1.现将其上三角中的元素按列优先顺序存放在一堆数组 B 1.。已知 B 1的地址为 100，每个元素占用 2 个存储单元，则 A 3， 4的地址为（ ） A 116 B 118 C 120 D 122 8一个带权的无向连通图的最小生成树（ ） A有一棵或多棵 B只有一棵 C一定有多棵 D可能不存在 9下列有关图遍历的说法中不正确的是（ ） A连通图的深度优先搜索是一个递归过程 B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C非连通图不能用深度优先搜索法 D图的遍历要求每一顶点仅被访问一次 10在最坏的情况下，查找成功时二叉排序树的平均查找长度（ ） A小于顺序表的平均查找长度 B大于顺序表的平均查找长度 C与顺序表的 平均查找长度相同 D无法与顺序表的平均查找长度比较 11闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（ ） A同义词之间发生冲突引起的 B非同义词之间发生冲突引起的 C同义词之间或非同义词之间发生冲突引起的 D散列表“溢出”引起的 12从外存设备的观点看，存取操作的基本单位是（ ） A逻辑记录 B数据元素 C文件 D物理记录 13对文件进行检索操作时，每次都要从第一个记录开始的文件是（ ） A顺序文件 B索引文件 C顺序索 引文件 D散列文件 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插入排序 二、填空题（本大题共 13 小题，每空 2 分，共 26 分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、 _和散列存储方第 11 页 式。 17设某非空双链表，其结点形式为 若要删 除指 针 q 所指向的结点，则需执行下述语句段： q-q-_。 18如图所示，设输入元素的顺序是 A， B， C， D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为 D，则输出序列为 _。 19队列中允许进行删除的一端为 _。 20设一棵二叉树中度为 2 的结点数为 10，则该树的叶子数为 _。 21如图所示的二叉树，若按后根遍历，则其输出序列为 _。 22一个具有 n 个顶点的有向完全图的弧数为 _。 23查找表的数据结构有别于线性表、树型结构等，其逻辑结构为 _。 24长度为 L 的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为 _。 25在开散列表上查找某元素时，通常分两步进行，首先必须计算该键值的散列地址，然后在地址指针所指_中查找该结点。 26文件的检索有顺序存取、 _和按关键字存取三种方式。 27在待排序的 n 个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为 _。 28在对一组记录关键字（ 54， 38， 96， 23， 15， 72， 60， 45， 83）进行冒泡排序时，整个冒泡排序过程中需进行_趟才能完成。 三、 应用题（本大题共 5 小题，共 30 分） 29设有一顺序队列 量为 5，初始状态时 ，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（ 6 分） （ 1） d,e,b 入队 （ 2） d,e 出队 （ 3） i,j 入队 （ 4） b 出队 （ 5） n,o,p 入队 30已知无向图 G 的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从 始的深度优先搜索的序列。（ 4 分） 第 12 页 431画出下列二叉树的二叉链表表示图。（ 6 分） 32用二分查找法对一个长度为 10 的有序表进行查找，填写查找每一元素需要的比较次数。（ 8 分） 元素下标 1 2 3 4 5 6 7 8 9 10 比较次数 33已知序列（ 10， 18， 4， 3， 6， 12， 1， 9， 15， 8），请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。（ 6 分） 四、设计题（本大题共 2 小题，共 14 分） 34设某带头结头的单链表的结点结构说明如下： 试设计一个算法： l, )，将以 为头指针的单链表复制到一个不带有头结点且以 头指针的单链表中。（ 6 分） 35修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾，第二次把最小记录放到表头，如此反复进行。试编写修改后的算法： a,n)。（ 8 分） 第 13 页 2003 年 10 月数据结构导论试题答案 第 14 页 第 15 页 第 16 页 全国 2004 年 10 月高等教育自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 转化过程依次为（ ） 储结构、机外表示 辑结构、机外表示 辑结构、存储结构 储结构、逻辑结构 较对数阶量级与线性阶量级，通常（ ） 于加工型的操作是（ ） 表长度、插入操作 入、删除操作 元素、定位操作 入、删除操作 p 所指结点不是最后结点， s 指向已生成的新结点，则在 p 之后插入 s 所指结点的正确操作是（ ） pps; ssp; p; ps; pp=s; 其所有可能的输出排列共有（ ） 言对数组元素的存放方式通常采用（ ） 的叶子结点其度数（ ） 0 对于 n 个结点的二叉树一定有（ ） 指针域其中 n 个指针为 指针域其中 n+1 个指针为 指针域其中 n 个指针为 指针域其中 n+1 个指针为 有顶点的度数之和等于边数的（ ） 图的广度优先搜索类 似于二叉树的（ ） 在表头设置岗哨，则正确的查找方式通常为（ ） 个元素开始往后查找该数据元素 个元素开始往后查找该数据元素 n 个元素开始往前查找该数据元素 n+1 个元素开始往前查找该数据元素 率最高的查找方法是（ ） 构成，其中（ ） 第 17 页 时间复杂性为（ ） ) B.O(n) C.O( D.O(于稳定的排序方法是（ ） 二、填空题（本大题共 13 小题，每小题 2 分，共 26 分） 请在每小题的空格中填上正 确答案。错填、不填均无分。 据通常可分为三个层次，即：数据、数据元素和 _。 程序设计语言并混合自然语言描述的算法称为 _算法。 插入算法的平均时间复杂性为 _。 n 个单元、且采用顺序存储的循环队列中，队满时共有 _个元素。 20.若 别表示循环队列 Q 的头指针和尾指针， 示该队列的最大容量，则循环队列为空的条件是_。 1020采用按行为主序的存储方式，每个元素占 4 个存储单元，若 A00的存储地址为 300，则A1010的地址为 _。 根遍历和 _三种。 k 的完全二叉树至少有 _个结点。 该图一定是一个 _。 n 个元素的数据序列，采用二叉排序树查找，其平均查找长度为 _。 免散列所产生的“堆积”现象，通常采用 _法。 中文含义为 _方法。 于具有 n 个元素的有序序列，若采用冒泡排序，所需的比较次数为 _次。 三、应用题（本大题共 5 小题，每小题 6 分，共 30 分） 给出其二叉链表及顺序存储结构表示。 的邻接表如图所示，试给出以顶点 出发点，按广度优先搜索所产生的一棵生成树。 0 个结点的值依次为 110，其 结构如图所示，试标出该二叉树各结点所对应的具体值。 第 18 页 28， 47， 35， 42， 53， 60， 34， 22），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。 3， 6， 8， 9， 2， 7， 4， 3），试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。 四、设计题（本大题共 2