发布时间 : 星期一 文章2016现代科技学院《软件技术基础》练习题+答案更新完毕开始阅读62d9a7af77232f60dccca1ab
14. 在以下的叙述中，正确的是【 】。
A．线性表的线性存储结构优于链式存储结构
B．二维数组是它的每个数据元素为一个线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 15. 以下说法正确的是【 】。
A．数据元素是数据的最小单位 B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合 D．数据结构是带有结构的数据元素的集合
16. 线性表L=(a1，a2，?，ai，?，an)，下列说法正确的是【 】。
A．每个元素都有一个直接前驱和直接后继 B．线性表中至少要有一个元素
C．表中诸元素的排列顺序必须是由小到大或由大到小的
D．除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 17. 对于顺序线性表的优缺点，以下说法错误的是【 】。
A．无需为表示结点间的逻辑关系而增加额外的存储空间 B．可以方便地随机存取表中的任一结点 C．插入和删除操作较方便
D．由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
18. 在含有n个结点的顺序存储的线性表中，在任一结点i前插入一个结点所需移动结点的次数为【 】。
A．n/2 B．i C．n-i D．n-i+1
19. 在含有n个结点的顺序存储的线性表中，删除第i个结点所需移动结点的次数为【 】。 A．n/2 B．i C．n-i D．n-i+1
20. 在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为【 】。
A．n B．n/2 C．(n-1)/2 D．(n+1)/2
21. 在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为【 】。 A．n B．n/2 C．(n-1)/2 D．(n+1)/2 22. 带头结点的单链表为空的条件是【 】。
A．head=NULL B．head->next=NULL C．head->next=head D．head!=NULL 23. 在一个单链表中，若删除*p结点的后继结点，则执行【 】。
A．q=p->next；p->next=q->next；free(q)；
B．p=p->next；p->next=p->next->next；free(p)； C．p->next=p->next；free(p->next)； D．p=p->next->next；free(p->next)； 24. 循环链表的主要优点是【 】。
A．不再需要头指针了
B．已知某个结点的位置后，容易找到它的直接前驱 C．在进行插入、删除操作时，能更好地保证链表不断开 D．从表中任一结点出发都能扫描到整个链表
25. 在线性表的下列存储结构中，读取元素花费时间最少的是【 】。
A．单链表 B．双链表 C．循环链表 D．顺序表
26. 设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为a2,a4,a3,a6,a5,a1，则栈S的容量至少应该为【 】。 A．2 B．3 C．5 D．6
27. 二维数组A[11，6]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[0，0]的存储地址是1000，则A[8，4]的存储地址是【 】。
5
A．1208 B．1212 C．1368 D．1364 28. 对矩阵压缩存储是为了【 】。
A．方便运算 B．节省空间 C．方便存储 D．提高运算速度 29. 以下说法错误的是【 】。
A．树形结构的特点是一个结点可以有多个直接前驱 B．线性结构中的一个结点至多只有一个直接后继 C．二叉树与树是两种不同的数据结构
D．树(及一切树形结构)是一种“分支层次’结构 30. 以下说法错误的是【 】。
A．二叉树可以是空集
B．二叉树的任一结点都有两棵子树 C．二叉树与树具有相同的树形结构
D、二叉树中任一结点的两棵子树有次序之分
31. 一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递减序列。
A．前序 B．中序 C．后序 D．层次
32. 对含有【 】个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A．0 B．1 C．2 D．不存在这样的二叉树
33. 已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是【 】。 A．acbed B．baedc C．dceab D．cedba
34. 某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是【 】。
A．bdgcefha B．gdbecfha C．bdgechfa D．gdbehfca 35. 在图6-2中的二叉树中，【 】不是完全二叉树。
36. 树最适合用来表示【 】。
A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据
37. 在计算递归函数时，如不使用递归过程，则一般情况下必须借助于【 】数据结构。 A．栈 B．树 C．双向队列 D．顺序表
38. 对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【 】。 A．N B．(N-1)*(N-1) C．N-1 D．N*N 39. 以下说法错误的是【 】。
A．用邻接矩阵法存储图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关
B．邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用 C．存储无向图的邻接矩阵是对称的，因此也可以只存储邻接矩阵的下(或上)三角部分 D．用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可
6
二、填空题
1. 通常，数据在计算机中的存储结构有_____存储结构、______存储结构、______存储结构和_____存储结构四种基本存储结构。
2. 设循环队列的容量为70（序号为1~70），现经过一系列的入队与退队运算后，有： ①. front = 14，rear = 21，循环队列中有______个元素 ②. front = 23，rear = 12，循环队列中有______个元素
3. 单链表表示法的基本思想是用______表示结点间的逻辑关系。 4. 栈的逻辑特点是______，队列的逻辑特点是______ 5. ______可以作为实现递归函数调用的一种数据结构。 6. 在队列中，新插入的结点只能添加到______。
7. 设用一维数组A[n]来表示一个栈，令A[0]为栈底。用整型变量t来指示当前栈顶的位置，A[t]为栈顶元素。往栈中压入一个新元素时，变量t的值______，从栈中弹出一个元素时，变量t的值______。设空栈时，输入序列a，b，c经过push，pop，push，push，pop操作后，从栈中弹出的元素是_____。
8. 树(及一切树形结构)是一种_____结构。在树中，______结点没有直接前驱。 9. 二叉树第i(i>0)层上至多有______个结点。 10. 深度为k(k>0)的二叉树至多有______个结点。
11. 二叉树通常有_______存储结构和_____存储结构两类存储结构。 12. 对二叉链表的访问只能从______指针开始。
13. 对无向图，其邻接矩阵是一个关于_______对称的矩阵。
14. 请填空完成线性表在顺序存储下的插入运算程序：在线性表v中第i个位置插入值为x的元素 struct sqlist
{ int elem[MAXSIZE]; int last;
};
void insert(sqlist v, int i, int x) { int k; if (i<1 || i>v.last+1) printf( ''插入位置不合适！\\n'' ); else if (v.last>= MAXSIZE -1) printf( ''线性表已满！\\n'' ); else { for( k = v.last; k >= i; k-- ) _______________________ v.elem[i] = x; v.last++; }
}
15. 请填空完成线性表在顺序存储下的删除运算程序：在线性表v中删除第i个位置的元素
struct sqlist { int elem[MAXSIZE]; int last;
};
7
void delete(sqlist v, int i) { int k; if (i<1 || i>v.last)
printf( ''删除位置不合适！\\n'' ); else { for( k = i+1; k <= v.last; k++ ) v.elem[k-1] = v.elem[k]; _______________________ } }
16. 请填空完成栈在顺序存储下的入栈运算程序：将值为x的元素入栈s struct stack
{ int sData[MAXSIZE];
int top; //栈顶指针，指向当前栈顶的位置 };
void push(struct stack s, int x) //入栈运算 { if (s.top == MAXSIZE-1) { printf(''栈满溢出 \\n''); } else { _______________________ s.sData[top]=x; } }
17. 请填空完成栈在顺序存储下的出栈运算程序：栈s出栈，并将出栈元素作为函数返回值返回struct stack
{ int sData[MAXSIZE];
int top; //栈顶指针，指向当前栈顶的位置 };
int pop(struct stack s) //退（出）栈运算 { int x; if (s.top == -1) { printf(''栈空溢出 \\n''); exit(1); } else { x=s.sData[top]; _______________________ } return x; }
8