1 / 5玉林师范学院期中课程考试试卷（2010——2011学年度第一学期）命题教师：刘恒 命题教师所在系：数计系课程名称：数据结构考试专业：计算机考试年级：09级一、单项选择题（每题2分，共30分，把正确答案填入表格中） 1、下列哪项不是衡量算法优劣的规范( )。
A 、健壮性B 、可行性C 、可读性D 、效率与低存储量2、设n 为正整数，则下列程序段中前置以记号@的语句频度为( )。
k=0。
for(i=1。
i<=n 。
i++) { for(j=i 。
j<=n 。
j++) @ k++。
}A 、2nB 、n-1C 、n(n+1)/2D 、n3、关于线性表()n a a a ,...,,21的说法，下列哪个是不正确的( )。
A 、数据元素同构。
B 、数据元素个数n 为表长度。
C 、当n=0时，线性表为空表。
D 、数据项能出现缺项。
4、在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。
A 、基地址和结点大小B 、结点大小C 、基地址D 、向量大小5、在( )运算中，使用顺序表比链表好。
A 、插入B 、删除C 、根据序号查找D 、根据元素值查找6、设N 为正整数，试确定下列程序段中前置以记号@语句的频度为( )。
x=91。
y=100。
while(y>0){@if(x>100){x-=10。
y-=2。
} else x++。
} A 、1100B 、550 C 、110D 、 557、“假上溢”现象会出现在( )中。
A 、循环队列B 、链队列C 、栈D 、顺序队列8、对单链表执行下列程序段，请选出不正确的一项( )。
T=Q 。
While(T->next!=NULL){T->data=T->data*3。
T=T->next 。
} A 、R->data=27B 、Q->data=12C 、H->data=2D 、P->data=39、一个栈的入栈序列是abcde ，则栈的不可能的输出序列是( )。
系(院): 年级: 专业: 班别: 学号: 姓名: 座位号: —————————————————————————————————————————————————————— 密 封 线 内 不 要 答 题∞ 装 订∞ 线 ∞A、edcbaB、decbaC、dceabD、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、设数组B[1..3，1..5]中的任一元素均占4个单元，从首地址SA=2010开始把数组B按列优先存储，则元素B[2，4]的地址为( )。
A、2042B、2074C、2050D、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、数据结构是一门研究____________的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
（非数值计算）2、空间复杂度作为算法所需存储空间的量度，记作____________。
（S(n)=O(f(n))）3、一个顺序表的开始地址是1000，每个元素的长度是8，则第7个元素的存储地址是____________。
（1048）4、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在____________结点的next域中。
（前驱）5、当程序中同时使用_______ _____个栈时，让它们共享同一向量空间可减少上溢的发生。
（2）6、假设以数组Sq[M]存放循环队列，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含的元素个数，则判别队满的条件是____。
（quelen= =M）7、假设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占____________个字节。
（4）8、在多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。
因此，数组是一种____________存取结构。
（随机）9、矩阵的压缩存储就是为多个相同的非零元素分配_____ ____个存储空间，不为零元素分配空间。
（1）10、广义表是线性表的推广，它们之间的区别在于_____ ____。
（能否使用子表）三、名词解释（每题2分，共10分）1、算法的可行性一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
（2分）2、数据项有独立含义的数据最小单位，也称域。
（2分）3、顺序表用一组地址连续的存储单元存放一个线性表称为顺序表。
（2分）4、队列队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。
（2分）5、空串零个字符的串称为空串。
（2分）2 / 5四、解答题（每题5分，共40分）1、在选择算法时，除首先考虑正确性外，还应考虑哪三点?选用的算法首先应该是"正确"的。
此外，主要考虑如下三点：①执行算法所耗费的时间；（2分）②执行算法所耗费的存储空间，其中主要考虑辅助存储空间；（1分）③算法应易于理解，易于编码，易于调试等等。
（2分）注：酌情给分。
2、请写出在结点a、b之间插入结点x的关键语句，设指针变量P指向结点b，指针变量S指向结点x。
void ins_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、如何解决顺序队列的假上溢问题？（1）基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0。
（2分）（2）实现：[入队]sq[rear]=x。
rear=(rear+1)%M。
[出队]x=sq[front%M]。
front=(front+1)%M。
（3分）注：只答出用循环队列解决的给1分。
5、下列算法为简单的串模式匹配算法，请填空完成。
int Index(SString S, SString T, int pos){i=pos。
j=1。
while(i<=S[0]&&j<=T[0]){if(_____ ____) {++i。
++j。
}else{_____ ____。
j=1。
}}if(j>T[0]) return i-T[0]。
else return 0。
}S[i]= =T[j] (2分)i=i-j+2 (3分)6、二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标的范围从1到10，则存放M至少需要多少个字节？若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先的方式存储时的什么元素的起始地址一致？540个字节。
（2分）M[3][10] （3分）7、请画出下列稀疏矩阵的十字链表。
3 / 54 / 5⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡-2000001000503001 （答案略） 8、设head[p]为求广义表p 的表头函数，tail[p]为求广义表p 的表尾函数，其中[]是函数符号，给出下列广义表的运算结果。
(1) head[tail[(a,b,c)]](2) tail[head[((a,b),(c,d))]] (3) head[head[((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.listsize) return(overflow)。
（1分） else{i=a.length-1。
（1分） while(i>=0&&x<a.elem[i])i--。
（1分） for(j=a.length-1。
j>=i+1。
j--) （1分） a.elem[j+1]=a.elem[j]。
（2分） a.elem[i+1]=x 。
（2分） a.length++。
（1分） return OK 。
} }5 / 5。
