资源描述：
《计算机水平考试-中级软件设计师上午试题分类模拟1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、中级软件设计师上午试题分类模拟1单项选择题1>以下关于线性表采用链式存储时删除结点运算的描述，正确的是A.带头结点的线性链表删除结点时，不需要更改头指针B.带头结点的线性链表删除第一个结点吋，需要更改头指针C.不带头结点的线性链表删除结点时，需要更改头指针D・不带头结点的线性链表删除第一个结点时，不需要更改头指针2、给定一个右盯个元索的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动个元素。A.(巾+1)2B.(”+1)2D・13、下列叙述中，不止确的是oA.线性表在链式存储吋，查找第i个元索的吋间与i的值成正比B.线性表在链式存储时，查找第i个元素
2、的时间与i的值有关C.线性表在顺序存储时,D.线性表在顺序存储时,查找第i个元素的时间与i的值成•正比查找第i个元索的时间与i的值无关4、双向循环链表中，在p所指向的结点Z后插入s指向的结点，其修改指针的操作是,其中p指向的不是最后一个结点。A.p->next=s；s->prey=p；p->next->prev=s；s->next=p->next；B.p->next->prev=s；p->next=s；s->prev=p；s->next=p->next；C.s->prev=p；s->next=p->next；p->next=s；p->next->prev=s；D-s->prev=p
3、；s->next=p->next；p->next->prev=s；p->next=s；5、若元索“b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是oA.deebfaB・cbdaefC・bcaefdD.afedcb6、一个栈的入栈元索序列是1、2、3、4、5,若允许出栈操作可在任意可能的时刻进行，则下面的序列中，不可能出现的出栈序列是oA.3、4、2、5、1B・2、5、4、1>3C・2、3、1>5、4D.3、5、4、2、17、下面二叉树小一定是完全二叉树的是A.平衡二叉树B.满二叉树C.单枝二叉树D.二叉排序树在一棵度为4
4、的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点的个数是oA.41B.82C.113D.1229、已知某二叉树的先序序列为abode,它可能的屮序序列为oA.bdaecB.bcadeC.ecadbD.beacd10.-棵度为3的树中，有3度结点100个，有2度结点200个，有叶子结点个。IK在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：■丿asl=2?ec/=]此处巳为表小第i个记录被查找的概率，q为查找第i个记录时同关键字比较的次数，n为表中记录数。以下叙述中均假定每一个记录被查找的概率
5、相等，即P1=l/n(i=lz2…n)。当表中的记录连续有序存储在一个一维数组中吋，采用顺序查找与折半查找方法查找的ASL值分别是oA・D(n),D(n)B.O(n),0(1bn)C・O(nlbn),O(n)D.O(1bn),O(1bn)12、根据使用频率，为5个字符设计哈夫曼编码不可能是oA・111,110,10,01,00B・000,001,010,011,1C・001,000,10,01,11D・110,100,101,11,113、二叉树在线索化后，仍不能有效解决的问题是oA.先序线索二叉树小求先序后继B.屮序线索二叉树中求中序后继C.屮序线索二叉树中求中序前驱D.后序线索
6、二乂树中求后序后继14、由元素序列(27,16,75,38,51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为oA.27B.38C.51D.7515、若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有个顶点。A.11B.10C.9D・817.设下三角矩阵(上三角部分的元素值都为0)A[0・・H,0.・n]如图所示，将该三角矩阵的所有非零元索(即行下标不小于列下标的元索)按行优先压缩存储在容量足够人的数组M[]中(下标从1开始)，则元素A[i,j](OWiWn,jWi)存储在数组M的中。Ai,（）A]jA”oA
7、yjA?,2…•Az,?氏,0As,IAs.2傀・3•…As・8_F三角矩阵m[彎22十丿+i]A.ZM[写2+力B.L"「,（,一1）・7—+j]c.⑷？+丿+1]18、在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列VQ,H,CZY,P,A,M,S,R,D,F,X＞中的关键码按字母的升序重新排列，则是冒泡排序一趟扫描的结果。A.F,H,C,D,P,A,M,Q,R,S,Y,XB.P,A,C,S,Q,D
