资源描述：
《数据结构A卷模拟》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构A卷模拟一、选择题(A)4.算法分析的两个主要方面是：A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性(B)4•向一个冇127个元素的顺序表中插入一个新元素并保持原來顺序不变，平均要移动—个元索(A)8(B)63.5(C)63(D)7(B)8.线性表L在情况下适用于使用链式结构实现。(A)需经常修改L中的结点值(C)L中含有大量的结点(B)10.设al、a2、a3为3个结点,结构称为(B)需不断对L进行删除插入(D)L中结点结构复杂整数Po,3,4代表地址,则如下的链式存储Po3Poal39a24A30(A)循坏链
2、表(B)单链表(C)双向循坏链表(D)双向链表(C)2.K李春葆』若已知一个栈的入栈序列是1,2,3,…，m其输出序列为pl,p2,p3,…，pn,若pl=n,则pi为A.iB.n=iC.n-i+lD.不确定解释：当pl=n,即n是最先出栈的，根据栈的原理，n必定是最后入栈的(事实上题目已经表明了),那么输入顺序必定是1,2,3,…，n,则出栈的序列是n,…，3,2,1。(若不要求顺序出栈，则输出序列不确定)(B)1.K李》串是一种特殊的线性表，其特殊性体现在：A・可以顺序存储B.数据元索是一个字符C.可以链式存储D.数据元素可以是多个字符(B)5.设矩阵A是一
3、个对称矩阵，为了节省存储，将英下三角部分(如下图所示)按行序存放在一维数组B[l,n(n-l)/2]屮，对下三角部分屮任一元素％(iWj),在一维数组B中下标k的值是：A.i(i-l)/2+j-lB.i(i-l)/2+jC.i(i+l)/2+j-lD.i(i+l)/2+j^2,2解：注意B的下标要求从1开始。先用笫一个元素去套用，可能有B和C；再川第二个元素去套用B和C,B=2而C=3(不符);所以选B7.【96程试题1】二叉树的基木组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种:前序法（即按NLR次序），后序法（即
4、按—LRN次序）和中序法（也称对称序法，即按LNR次序）。这三种方法相互Z间有关联。若已知一棵二叉树的前序序列是BEFCGDH,屮序序列是FEBGCHD,则它的后序序列必是FEGHDCBo解：法1：先由已知条件画图，再后序遍历得到结果：法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前序先确定root,rfl小序先确定左子树。例如，前序遍历BEFCGDH屮，根结点在最前面，是B；则示序遍历中B—定在最丿口面。4.【全国专升本统考题】设一棵完全二叉树有700个结点,则共有350个叶子结点。答：最快方法：用叶了数=［口/2］a.0243156（C）3.H0
5、1年计算机研题H具：B.0136542（A）riog2（n）l（B）Lloc.0423165注1：「x］表示不小于x的授小整数；d.0361542注2：选（A）是错课的。例如当n为义树的深度为o（D）riog2（n）+ll整数，它们与□含义不同！昙。似乎Llog2（n）+l」是对的?）&已知图的邻接矩阵，根:建议：0134256姑发按深度优先遍历的结点序法3：递归计算。如B在前序序列中笫一，中序中在中间（可知左右了树上冇哪些元素），则在后序中必为授后。如法对B的左右子树同样处理，则问题得解。列是0111001001101010001101101100101000
6、110101000101101（C）2.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为A.希尔排序B.冒泡排序C.插入排序D.选择排序（D）3.从未排序序列屮挑选元索，并将具依次插入已排序序列（初始时为空）的一端的方法，称为A.希尔排序B.归并排序C.插入排序D.选择排序二，填空题1•在顺序表中插入或删除一个元素，需要平均移动表中•半元素,具体移动的元素个数与一表长和该元索在表屮的位直有关。2.线性表中结点的集合是一有限的,结点间的关系是一一对一的。3.向一个氏度为n的向虽的第i个元索
7、（1主n+l）Z前插入一个元索时，需向后移动n・i+l个元素。4.向一个长度为n的向量中删除笫i个元素（lSiWn）时，需向丽移动n・i个元素。6.【98初程P71】从供选择的答案中，选出应填入下面叙述_?内的绘确切的解答,把相应编号写在答卷的对应栏内。设有4个数据元素al、a2、a3和a4,对他们分别进行栈操作或队操作。在进栈或进队操作时，按al、a2.a3>a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，岀栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元索是A,第二次出栈得到的元素是B是;类似地，考虑对这四个数据元素进
8、行的队操作是进队两次，出
