— :号—位—座— — — — — — :名—姓—— — —题 — — — —答 — :号— 学— —要 — — — —不 — :别— 班— —内 — — — —线 — :— 业— 专—封 — — — —密 —:级—年— — — — — — :)—院—(系—— ∞考 试 时 间 { int i, x=0; 年 月 日 玉林师范学院期中课程考试试卷
上午8：00-10：00 （2014——2015学年度第一学期）
for (i=0;i<5;i++)
for (j=1;j<=n;j++) 命题教师：杨夏妮 命题教师所在院：计算机科学与工程学院 x+=2; 课程名称：数据结构 考试专业：计算机、软件工程 考试年级：2013级
return x; 线}
题 号 一 二 三 四 五 总 分 5
A、O(n) B、0(n) C、0(5n
) D、0(n2
) 应得分 30 10 10 40 10 满分：100 实得分 评分： 6、从逻辑上，可以将数据结构分为( )两类。
评卷人 A、动态结构和静态结构 B、顺序结构和链式结构 签 名 C、线性结构和非线性结构 D、逻辑结构和存储结构 得 分 7、关于链表的说法，请选出正确的一项( )。 一、单项选择题（每题2分，共30分，把正确答案填入表格中） A、逻辑相邻、物理相邻 B、可实现随机存取 C、存储空间使用紧凑 D、表容量易于扩充 1 2 3 4 5 6 7 8 8、对单链表执行下列程序段，请选出不正确的一项( )。
∞ H 2 5 7 3 8 ┅ 4 ^ 订9 10 11 12 13 14 15 P Q S R 1、线性表中( )只有一个直接前驱和一个直接后继。 T=P;
A、首元素 B、尾元素 While(T->next!=NULL){T—>data=T—>data*2;T=T—>next;} C、中间的元素 D、所有的元素
A、R->data=8 B、P->data=10 2、结构中的数据元素之间存在一个对多个的关系，称为( )结构。 C、S->data=16 D、Q->data=14
A、线性 B、树形 9、设依次进入一个栈的元素序列为d，a，c，b，不可得到出栈的元素序列( )。 C、图状 D、网状 A、d，c，b，a B、a，b，d，c 3、下面关于空串和空格串的描述错误的是( )。
C、a，b，c，d D、d，b，c，a
装A、空串长度为0 B、空格串长度大于等于1
10、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用( )存 C、空串无字符 D、空格串里面的字符可以是任意字符 储方式节省时间。
4、广义表(a,((b,( )),c),(d,(e)))的深度是( )。 A、单链表 B、双向链表 A、5 B、4 C、3 D、2 C、单循环链表 D、顺序表 5、下列算法suanfa2(n)的时间复杂度为( )。 11、( )是‘Yu**Jia**Shan’的子串。。
∞ int suanfa2(int n)
A、Yu B、‘jia’ C、‘**Shan’ D、‘YuJiaShan’
计算机、软件工程专业2013级《数据结构》期中考试试卷 第 1 页 （共 3 页）
12、下列说法哪个是不正确的：( )。
A、数据元素由若干数据项组成 B、栈的表头端称为栈顶 C、循环队列可解决假溢出问题 D、队列的表头端称为队头
13、假设二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（a11的基地址）为1000，按列存储时，元素a47的第一个字节的地址是（ ）。
A、1234 B、1276 C、1186 D、1360 14、组成数据的基本单位是（ ）。
A、数据项 B、数据类型 C、数据元素 D、数据变量 15、算法应具有的特点不包括( )。 A、确定性 B、有输入、输出 C、可行性 D、一一对应性
得 分 二、填空题（每题2分，共10分）
1、有广义表L6=( ( ( (apple),pear ),banana ),orange )，GetTail (GetHead(GetHead(L6)))=____________。
2、设串s=‘ABCDEFG’，则StrEmpty(StrClear(s))的结果是____________。 3、对稀疏矩阵进行压缩存储的目的是__ ______ __。
4、在双向链表的结点中有两个指针域，其一指向______________，另一指向______________。
5、栈的特点是______________，队列的特点是________________。
得 分 三、判断题（每题1分，共10分，对的打√，错的打×，把正确答案填入表格中） 3、栈顶元素一定是最先入栈的元素。（ ）
4、循环队列中的元素个数随队头指针与队尾指针的变化而动态变化。（ ） 5、只有当两个串的长度相等，并且各个对应位置的字符都相等时，则称这两个串是相等的。（ ） 6、不论是入队操作还是入栈操作，在链式存储结构上都需要考虑“溢出”情况。（ ） 7、在表长为n的顺序表中插入或删除一个数据元素的时间复杂度均为O(n)。（ ） 8、串的基本操作StrAssign，SubString和StrCompare的返回值结果都是字符串。（ ） 9、对称矩阵的压缩存储，可将n2个元压缩存储到n(n-1)/2个元的空间中。（ ） 10、在广义表中，任何一个非空列表其表头可能是原子，也可能是列表，而
其表尾必定为列表。（ ）
得 分
四、解答题（每题8分，共40分）
1、下面程序段的功能实现栈顶元素出栈，并用x返回其值，要求在下划线处填上正确的语句。 #define MAXSIZE 100 typedef int ELEMTYPE;
typedef struct {ELEMTYPE data[MAXSIZE]; int top;int base;} SqStack; void Pop(SqStack *stack,int x) {
if (stack->top==stack->base)
printf(“overflow”); else
{ _________________; _________________; } }
1 2 3 4 5 6 7 8 9 10 1、算法的效率只与问题的规模有关，而与数据的存储结构无关。（ ） 2、线性表的链式存储结构的存储空间一般要少于顺序存储结构。（ ）
计算机、软件工程专业2013级《数据结构》期中考试试卷 第 2 页 （共 3 页）
2、已知P结点是某双向链表的中间结点，请写出在P结点之后插入S结点的语句序列：
．．． ．．． a b
Ｐ 3、设s=‘I AM A STUDENT’,t=‘GOOD’,q=‘WORKER’。 求：(1) StrLength(s)； (2) SubString(s,8,7)；
(3) Index(s,‘A’)； (4) Replace(s,‘STUDENT’,q)； (5) Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))。
5、画出广义表A=(a,(b,(c,d)))的存储结构图,并计算出广义表A的长度和深度。
得 分 五、算法设计题（1题，共10分）
已知线性表L用顺序存储结构来存储，且L中的数据元素是按值非递减有序排列，现在有一个元素e要插入到线性表L中，请编写算法将元素e插入到线性表L后使得线性表L中的数据元素仍按值非递减有序排列。
4、已知具有6行×7列的一个稀疏矩阵如下图所示：
?0400000??000?3001????8000000? ??
0005000???0?700020???0006000????请画出该稀疏矩阵以行序为主序的三元组表。
计算机、软件工程专业2013级《数据结构》期中考试试卷 第 3 页 （共 3 页）