数据结构3题答案

1、数据结构与算法模拟题3一、单选问题1 .计算机算法具有输入、输出和()五个特征。a .可行性、确定性和贫困性b .可行性、可移植性和可扩展性c .确定性、贫困性和稳定性d .易读性、稳定性和安全性2 .线性表的顺序记忆结构如何表现要素间的关系()。a .后续元素地址b .元素的存储顺序c .左、右孩子的地址d .后续要素的数组下标3 .描述算法的最佳语言是()a .自然语言b .计算机程序语言c .介于自然语言和编程语言之间的伪语言d .数学公式4 .使用连锁存储结构存储线性表的优点是()a .插入和删除操作容易b .随机访问容易c .比顺序存储占用的存储空间更少的d .数据元素的物理顺序与逻

2、辑顺序相同5 .对于散列函数H(key)=key%m，m通常应该取()a .足够大的数b .素数c .奇数d .偶数6 .从顺序堆栈中删除元素时，()a .删除元素，然后移动堆栈上的指针b .不论前后，都同时进行c .在删除元素之前移动堆栈上的指针d .谁先谁后都行7 .广义表(a )、(b ) )的末尾是()A. (b) B.b C.(b) D.()8 .有二维阵列A1020，采用以行顺序为主的存储结构，各要素占两个空间，第一要素的存储位置为100 (十进制)，要素A66的存储位置为()A.320 (十进制) B. 352 (十进制)C.300 (十进制) D. 232 (十进制)9 .对数

3、组经常进行的两个基本操作是()a .搜索和插入b .插入和修改搜索和修改c.d .创建和删除10 .如果某个二叉树的顺序遍历是a、b、d、c和e，那么其可能的顺序遍历序列为()A.B、c、a、d、E B.C、b、a、d、eC.B、d、a、e、C.B、e、a、c、d11 .在关于下图记忆的描述中，()是正确的。a .使用邻接表存储图表，占有的存储区域数与图表中的节点数无关，与边数无关b .用邻接表存储图表，占有的存储区域数与图表中的边数有关，与节点数无关c .用邻接矩阵法存储图表，占有的存储空间数与图表中的节点数无关，与边数无关d .用邻接矩阵法存储图表，占有的存储空间数与图表中的边数无关，与节

4、点数无关12 .如果文件是“局部秩序”或文件长度较小，则内部排序的最佳方法是()a .泡沫排序b .快速排序c .直接插入排序d .简单地选择排序二、填补问题1 .计算机算法具有输入、输出、可行性、贫困性和_五个特征。2 .数据的基本单位是：3 .在图形结构中，每个节点的前驱节点和后续节点可以包含_。4 .在单链表中，头节点的角色是.5 .队列有_的特征。6 .二维排列的两种顺序存储结构分别是以行顺序为主的方式和以_为主的方式。7 .稀疏矩阵的压缩存储只能存储。8 .广义表(a ) )的末尾是_ _。9 .具有七个节点的二叉树为_二叉树时，具有最小高度。10 .假设无向图g的顶点数为n，g至少

5、在_边上。11 .扫描二叉树可获得由该二叉树的所有节点组成的秩序系列。在拥有12.20个记录的序列中，采用起泡排名的最小比较次数是_。三、解答问题1 .请用c语言给出顺序堆栈(堆栈的顺序存储结构)的类型定义。2 .请试着将字符串的排列变更为“3*-ya/y”，将字符串的顺序变更为“3y-*ay/”，写入操作步骤。 (可以用x表示扫描字符串时一个字符一个字符地放入堆栈中的操作，用s表示从堆栈中取出字符并添加到新字符串的末尾的操作。 例如，如果ABC为BCA，则操作步骤为XXSXSS )。3 .以行顺序三维排列A232的所有要素存储在存储器中的顺序为主要排列。4 .用3、6、7、8、30作为叶节点

6、的值生成霍夫曼树，并且计算该树的带权路径长度。5 .一棵度为3的树，度为3的节点的数量为2，度为2的节点的数量为1，度为0的节点的数量是多少？6 .以关键字序列 12，2，16，9，10，8，20 为例，执行以下排序算法，分别写入各回合的排序结束时的关键字序列的状态。 (1)直接插入排序(2)快速排序四、算法问题1 .下一种算法的功能是创建具有开头节点的单个链表，并且在链表中存储序列表的现有元素。 请在空缺处填写适当的词语。将void a (链接列表la，sqlist )设置为la=(链接列表) malloc (大小(节点) )；La-next=NULL；(1)for (i=0； i=Lb.l

7、ength-1； 表示I )q=(链接列表) malloc (大小(节点) )；q-data=Lb.elemi；(2)(3)以下(4)以下2 .读下面的算法，并给出该算法的功能。voidaunknow (堆栈)/Q是局部变量-队列InitQueue(Q )while (！ 堆栈空间(s ) ) i=Pop(S) EnQueue(Q，I )以下while (！ 队列空间(q ) ) I=队列(q )推式(s，I )以下以下一、选择问题一、a二、二3、略四、a五、b6、略七、a八、b九、c十、c十一、c十二、a二、填补问题1 .确定性2 .数据元素3 .略4 .简单运算的实现5 .先进先出6 .序列7 .略8.()；9