《级计本数据结构期中考试卷(含答案).doc》由会员分享，可在线阅读，更多相关《级计本数据结构期中考试卷(含答案).doc（5页珍藏版）》请在金锄头文库上搜索。
1、考 试 时 间 2010年11月11日下午系(院): 年级: 专业: 班别: 学号: 姓名: 座位号: 密 封 线 内 不 要 答 题 装 订 线 玉林师范学院期中课程考试试卷（20102011学年度第一学期）命题教师：刘恒 命题教师所在系：数计系 课程名称：数据结构 考试专业：计算机 考试年级：09级题 号一二三四五总 分应得分3010104010满分：100实得分评分：评卷人签 名一、单项选择题（每题2分，共30分，把正确答案填入表格中）12345678BCDACBDA9101112131415CBADCBA1、下列哪项不是衡量算法优劣的标准( )。 A、健壮性 B、可行性 C、可读性 D
2、、效率与低存储量2、设n为正整数，则下列程序段中前置以记号的语句频度为( )。 k=0; for(i=1;i=n;i+) for(j=i;j0)if(x100)x-=10;y-=2;else x+;A、1100 B、 550 C、110 D、 557、“假上溢”现象会出现在( )中。A、循环队列 B、链队列C、栈 D、顺序队列8、对单链表执行下列程序段，请选出不正确的一项( )。H234555690PQRST=Q;While(T-next!=NULL)T-data=T-data*3;T=T-next;A、R-data=27 B、Q-data=12 C、H-data=2 D、P-data=39、
3、一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。 A、edcba B、decba C、dceab D、abcde10、在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是( )。 A、R=F-next; B、F=F-next; C、R=R-next; D、F=R-next;11、串是一种特殊的线性表，其特殊性体现在( )。 A、数据元素是一个字符 B、可以顺序存储 C、可以链接存储 D、数据元素可以是多个字符12、设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。 A、线性表的顺序存储结构 B、队列 C、线性表的链式存储结构 D、栈13、设
4、数组B1.3，1.5中的任一元素均占4个单元，从首地址SA=2010开始把数组B按列优先存储，则元素B2，4的地址为( )。 A、2042 B、2074 C、2050 D、210814、对稀疏矩阵进行压缩存储是为了( )。 A、便于进行矩阵运算 B、节约存储空间 C、便于输入和输出 D、降低运算的时间复杂度15、下列说法哪个是不正确的：( )。 A、广义表(a)的表头是(a)。 B、广义表(a),(b),c),(d)长度为3。 C、广义表(a),(b),c),(d)深度为4。 D、广义表(a),(b),c),(d)的表尾是(b),c),(d)。二、填空题（每题1分，共10分）1、 数据结构是一
5、门研究_的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。（非数值计算）2、 空间复杂度作为算法所需存储空间的量度，记作_。（S(n)=O(f(n)）3、 一个顺序表的开始地址是1000，每个元素的长度是8，则第7个元素的存储地址是_。（1048）4、 在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在_结点的next域中。（前驱）5、 当程序中同时使用_ _个栈时，让它们共享同一向量空间可减少上溢的发生。（2）6、 假设以数组SqM存放循环队列，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含的元素个数，则判别队满的条件是_
6、_ 。（quelen= =M）7、 假设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占_个字节。（4）8、 在多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，数组是一种_存取结构。（随机）9、 矩阵的压缩存储就是为多个相同的非零元素分配_ _个存储空间，不为零元素分配空间。（1）10、广义表是线性表的推广，它们之间的区别在于_ _。（能否使用子表）三、名词解释（每题2分，共10分）1、算法的可行性一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（2分）2、数据项有独立含义的数据最小单位，也称域。（2分）3、顺序
7、表用一组地址连续的存储单元存放一个线性表称为顺序表。（2分）4、队列队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。（2分）5、空串零个字符的串称为空串。（2分）四、解答题（每题5分，共40分）1、在选择算法时，除首先考虑正确性外，还应考虑哪三点?选用的算法首先应该是正确的。此外，主要考虑如下三点： 执行算法所耗费的时间； （2分） 执行算法所耗费的存储空间，其中主要考虑辅助存储空间； （1分） 算法应易于理解，易于编码，易于调试等等。 （2分）注：酌情给分。2、请写出在结点a、b之间插入结点x的关键语句，设指针变量P指向结点b，指针变量S指向结点x。baPxSvoid ins
8、_dulist(JD *p,int x) JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; （以上1分） s-prior=p-prior; （1分） p-prior-next=s; （1分） s-next=p; （1分） p-prior=s; （1分）注：没有函数定义，只写出语句也可；大小写均可。3、把下列中缀表达式分别表示成后缀表达式。(1) a+(b*c+d)/e(2) a*b/c+d-e(3) a-b*c+d/e(1) abc*d+e/+ (1分)(2) ab*c/d+e- (2分)(3) abc*-de/+ (2分)4、如何解决顺序队列的假上溢
9、问题？（1）基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0。（2分）（2）实现：入队sqrear=x;rear=(rear+1)%M;出队x=sqfront%M;front=(front+1)%M。（3分）注：只答出用循环队列解决的给1分。5、下列算法为简单的串模式匹配算法，请填空完成。int Index(SString S, SString T, int pos)i=pos;j=1;while(i=S0&jT0) return i-T0;else return 0;Si= =Tj (2分)i=i-j+2 (3分)6、二维数组M的成员是6个字符（每
10、个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标的范围从1到10，则存放M至少需要多少个字节？若M按行优先方式存储，元素M85的起始地址与当M按列优先的方式存储时的什么元素的起始地址一致？540个字节。（2分）M310 （3分）7、请画出下列稀疏矩阵的十字链表。 （答案略）8、设headp为求广义表p的表头函数，tailp为求广义表p的表尾函数，其中是函数符号，给出下列广义表的运算结果。(1) headtail(a,b,c)(2) tailhead(a,b),(c,d)(3) headhead(a,b),(c,d)(1) b (1分)(2) (b) （2分）(3) a （2分）五、算法设计题：设顺序表Va中的数据元素非递减有序。写一算法将x插入到顺序表的适当位置上，以保持该表的有序性。（10分）status insertorderlist(sqlist &a,elemtype x) （1分）if(a.length=a.
