《自学考试-数据结构自考题模拟12》由会员分享，可在线阅读，更多相关《自学考试-数据结构自考题模拟12（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构自考题模拟12一、单项选择题K当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为()A r? B n_onan C log2n D. n-12、长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下,查找失败时的ASL值是()A. 37/12 B. 62/13 C. 39/12 D. 49/133、对广义表(a), (b)进行下面的操作head (head ( (a) , (b)后的结果是()AaB(a)C. () D.不确定4、顺序存储结构()A仅适合于静态查找表的存储B. 仅适合干动态查找表的存储C. 既适合静态乂适合动态查找表的存
2、储D. 既不适合静态又不适合动态查找表的存储5、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为()A. 42 B. 40C21 D206、非空的单循环链表L的尾结点Pt ,满足()A P t .next=NULL；B P=NULL；C P t next=L；D. P=L7、对长度为n的关键字序列进行堆排序的空间复杂度为()A Odogn B. 0(1)C O(n)D O(n*log2n)8、堆排序的最坏时间复杂度为()A. O(n)B OCLOg：!)C omiog?!) D. O (n2)9、在线性表的下
3、列运算中，不改变数据元素Z间结构关系的运算是()A.插入 B.删除 C.排序 D.定位10、深度为k的二叉树，所含叶子的个数最多为()A. 2K B KC 2K-1 D 2K-111对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第1个元素为基准的一次划分的结果 为 ()A. (5,1,4,3,6,2,8,7) B. (5,1,4,3,2,6,7,8)C. (5,1Z4Z3Z2Z6,8Z7) D. (8,7,6,5z4,3,2,1)条边。C N(N+1) D. N(N+1) /212、一个具有N个顶点的有向图最多有(A. N(N-l)/2 B. N(N-l)丄3、通常要求同一逻
4、辑结构中的所冇数据元素具冇相同的特性，这意味着（）A. 数拯元素具有同一特点B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C. 每个数据元索都一样D. 数据元素所包含的数据项的个数耍相等14、采用分治法进行排序的方法是（）A.快速排序B.插入排序C堆排序 D.希尔排序15、下列说法中正确的是（）A. 二叉树中任何一个结点的度都为2B. 二叉树的度为2C. 任何一棵二叉树中至少有一个结点的度为2D. 一棵二叉树的度可以小于2二. 填空题丄6、一个字符串相等的充耍条件是和o17. 当所有结点的权值都相等时，用这些结点构造的二叉排序树上只右。18、假设散列文件中一个桶能存放
5、m个记录，则桶溢出的含义是，当需要插入新的记录时，该桶中19、数组的长度是,线性表的长度是。20、对表长为9000的索引顺序表进行分块查找，假设每一块的长度均为15,且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为o21、多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是o22、假设以列优先顺序存储二维数组A5 8,其中元索A0 0的存储地址为LOC（a00）,冃每个元素占4个存储单元，则数组元素Ai j的存储地址为。23、一棵含999个结点的完全二叉树的深度为o24、控制区间和控制区域是文件的逻辑存储单位。25、对于数组，通常具有的基木操作有种，它
6、们分别是o三、解答题26、对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。57604p 10610一佃324543355402314-112140127、图的邻接表的类型定义如下所示：#define MaxVertexNum 50 typedef struct nodeint adjvex；struct node*next；EdgeNode； typedef structVertexType vertex；EdgeNode*firstedge；VertexNode；typedef VertexNode A djListMaxVertexNum； typedef structAd
7、j List adj iist;O-RTHTFIint n,e； ALGraph； 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储 表示实例如下图所示，请写出重新定义的类型说明。28、假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质 来分析二分查找的最坏性能和平均性能。29、某类物品的编号由一个大写英文字母及2位数字（0.9）组成，形如E32。运用基数排序对下列物 詁编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。E13ZA3 7Z F43ZB32,B47ZE12Z F37,B12第一趟：第二趟:第三梢:四.
8、算法阅读题（假设n为2的乘幕，并且n2）30、求下面算法中变量count的值: int Timeint ncount=0；x=2； while (xl)prinft(i-)；阅读下列算法，并回答问题：32rps = OneWor 1 dOneDream*, t=nOne, pos是一维整型数组，场出算法f32 (s, t z pos) 执行Z后得到的返回值和p。引I 的值；33简述算法f32的功能。int strlen (char*s) ； /*返冋串S的长度*/int index(char*st, char*t)；若串t在串st中出现，则返冋在串st中首次出现的下标值，否则返冋-/int f
9、32(char*s,char*t,int pos ) int i,j z kzIs,It；Is=strlen(s)；lt=strlen(t)；if (ls = = 0| | It = = 0)return-1；k=0 ；i = 0;do j =index(s + iz t)；if (j = 0) posk+ + =i +j ； i + = j +it; while (i + it D2 B3、A4、C5、D6、C7、B解析由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地 排序，辅助空间为0(1),但它是不稳定的。8、C9、D10、C1丄、C12、B13、 B14
10、、 A15、 D二、填空题16. 两个字符串的长度相等 对应位置的字符相等17.右子树18、已冇m个同义词的记录(或：已有m个记录；或：已满)19、固定的 可变的20、308.521.一个数据元素可能冇多个直接前趋和多个直接后继22、LOC(a00)+4(5j+i)23、1024、VSAM25、两查找和修改三、解答题26、从三元组表还原稀疏矩阵时，首先根据表的第1行得出稀疏矩阵的行数和列数，否则，我们无法 确定所求的稀疏矩阵的维数，然后根据三元组表所捉供的行号和列号在稀疏矩阵的对应位置上写上相 应的元素的值，在其他地方补零即可，根据上述原则，此题答案如图(1), (2)所示。rO030On-0
11、000-101-10000-100000000100000000000000D0450000100000003000O27、typeclef struct ArcNodeVNode*adj vex； /该弧所指向的顶点的位置 struct ArcNode*nextarc；/扌旨1句下一条弧fl勺扌旨针ArcNode;typedef struct VNodeVertexType data； /顶点信息struct VNode*nextVertex； /扌旨向下个顶点的扌旨钊.ArcNode *f irstarc； /指向第一条依附该顶点的弧VNode *Adj List； typedef str
12、uctAdjList adjList；int n,e； ALGraph；28、假设判定树的内部结点的总数为n=2h-lo则判定树是深度为h=lg(n+l)的满二叉树，树中第k层上的结点的个数为2,查找它们所需要比较的次数是k。则在等概率下，二分查找成功时的平均查找长度为：n,如果n很大，则可以用如下近似公式：lg(n+l)-l,作为二分杳找成功时的平均查找长度。二分查找在查找失败时所需要比较的关 键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判 定树中度数小于2的结点只可能在最下面的两层上，所以11个结点的判定树的深度和n个结点的完全二 叉树的深度相同，
13、即为lg(n+l),所以，二分查找的最坏性能和平均性能I分接近。29、 第一趟：B32,E12ZB12ZE13Z F43ZA37ZB47, F37第二趟：E12ZB12/E13ZB32ZA37Z F37z F43,B47第三趟：A37/B12/B32,B47ZE12,E13/ F37, F43四. 算法阅读题30、count = log2n31此递推过程可以改写成如卜-递归过程：voide dkui(int j)if (il)prind(j );digui (j-1);32、2； pos0=0, posl=833、返冋串t在S中出现的次数，并将每次出现的位置依次存放在数组posK五、算法设计题34、可先分别将A、B文件的内容读出放到数组C中，再对数组C排序，最后再将数组内容写到文件C 中，程序为：#includemain() 八合并A、B文件内容到C文件中*/ FILE*fp；int i,j,n,m；char c 160 ,t,ch；if(fp=fopen(nAz Hrn)
