数据结构_4_试题卷

1、山东工商学院2020学年第一学期数据结构课程试题A卷（考试时间：120分钟，满分100分）特别提醒：1、所有答案均须填写在960数字加起来827参考答案207上，写在试题纸上无效。2、每份答卷上均须准确填写函授站、专业、年级、学号、姓名、课程名称。一单选题（共20题，总分值40分）一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度 为0的结点有（）。（2分） TOC o 1-5 h z 5个6个7个8个设广义表 L=（a,（）,b,（c,d,e），则 Head（Tail（Tail（L）的值为（）。（2 分）bc（c）（c,d,e）下列关于文件的说法，错误的是（）

2、。（2分）选择文件的组织方式时应考虑外存的性质和容量不定长文件指的是总长度可变的文件对文件的操作主要是维护和检索文件的存储结构指的是文件在外存上的组织方式串的长度是指（）。（2分）串中所含不同字母的个数串中所含字符的个数串中所含不同字符的个数串中所含非空格字符的个数在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈 中压入一个数据元素时，top的变化是（）。（2分）不变top=ntop+top-设有无向图 G=（V,E）,其中顶点集合 V=a,b,c,d,e,f,边集合 E=（a,b）, （a,e）, （a,c）, （b,e）, （c,f）, （f,d）, （

3、e,d）。对G进行深度优先遍历，正确的遍历序列是（）。（2分）a,b,e,c,d,fa,c,f,e,b,da,e,b,c,f,da,e,d,f,c,b适用于折半查找的表的存储方式及元素排列要求为（）。（2分）链接方式存储，元素无序链接方式存储，元素有序顺序方式存储，元素无序顺序方式存储，元素有序顺序表中数据元素的存取方式为（）。（2分）随机存取顺序存取索引存取连续存取将两个各有n个元素的有序表归并成一个有序表，最少进行（）次比较。（2分） TOC o 1-5 h z n2n-12nn-1下列排序算法中（）不能保证每趟排序至少能将一个元素放到其最终的位置上。（2分）快速排序shell 排序堆排序

4、冒泡排序一棵二叉树中第6层上最多有（）个结点。（2分） TOC o 1-5 h z 2313264下列说法中错误的是（）。（2分）数据对象是数据的子集数据元素间关系在计算机中的映象即为数据的存储结构非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系抽象数据类型指一个数学模型及定义在该模型上的一组操作串是一种特殊的线性表，其特殊性体现在（）。（2分）可以顺序存储数据元素是一个字符可以链接存储数据元素可以是多个字符设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为（）。（2分） TOC o 1-5 h z 5025107下述文件中适合于磁带存储的是（）。（2分）

5、顺序文件索引文件散列文件多关键字文件设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的 操作是（）。（2分）rear=front-nextrear=rear-nextfront=front-nextfront=rear-next设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2,则G中弧数为（）。（2分） TOC o 1-5 h z 4条5条6条无法确定在待排元素序列基本有序的前提下，效率最高的排序方法是（）。（2分）插入选择快速归并设串s=abcdefgh，则其子串数为（）。（2分） TOC o 1-5 h z 837369设哈希表地址范围为01

6、9，哈希函数H（key）=key%17,使用二次探测再散列法处理冲突。若表 中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应 为（）。（2分） TOC o 1-5 h z 23478以上都不对二简答题供6题，总分值60分）设有上三角矩阵（aij）nXn,将其上三角元素逐行存于数组Bm中（m充分大），使得Bk=aij, 求用i和j表示k的下标变换公式。（10分）已知单链表L中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算法将 L分割为三个循环链表，其中每个循环链表只含一类字符。（10分）设给定关键字序列（68, 55, 27, 43, 58, 12），试构造平衡的二叉查找树。（10分）设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。（10分）设 a=data structure，b=computer，c=demo，试求：StrLength（a）的返回值；执行StrInsert（b,4,c）后串b的值；Index（a,u,10）的返回值； 执行 Replace（a,structure,b）后串 a 的值； 执行 SubString（s,b,3,3）后串 s 的值。（10 分）设内存有大小为5个记录的