一、简答与计算（每小题各5分 ）
1. 试举一实例，从逻辑结构、存储结构、算法三个层次简要说明数据结构的内涵。
2. 求下面算法的渐近时间复杂度。
int a(int n)
int i , j，y＝0；
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
y++;3. 上图为单链表，已知指针变量p和s， 若在p结点（即指针p所指向的结点）之后插入s结点及其后继结点，试写出相应语句实现此操作。
4. 在一个长度为n的顺序表中，在第i个元素（1≤i≤n）之前插入一个新元素，须向后移动多少个元素？（3分）
5. 二叉链表与孩子－兄弟链表的区别与联系。
二、判断对错并阐明原因（每小题各5分，判断1分，原因分析4分）
6. **性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上一定相邻。
7. 一棵二叉树的任一个非叶子结点的度为2，则该二叉树为满二叉树。
8. 二叉树是度为2的树。
9. 最大堆的前三个结点是堆中值最大的三个顶点。
三、问题求解。
10. 对于下面的每一步，给出栈的变化情况的示意图（6分）
（1）栈空 （2）元素a入栈 （3）x入栈（4）删除栈顶元素（5）g，k,l入栈。
11. 下图是一棵二叉树的顺序存储结构，试画出其二叉链表表示形式。（6分）
12. 已知一棵二叉树的先序和中序序列如下，构造出该二叉树。（6分）
先序序列：ebadcfhgikj 中序序列：abcdefghijk
13. 写出如下程序段的输出结果(队列中的元素类型 qelem type 为char)。
main (
queue q;
initqueue (q );
char x=’e’, y =’c’;
enqueue (q,’h’);enqueue (q,’r’);enqueue (q,y);
dequeue (q, x); enqueue (q,x);
dequeue (q, x); enqueue (q,’a’);
while (!queueempty (q))
｛ dequeue (q,y); cout < cout < 四编程（10分） 某商店有一批计算机，已知利用一个带头结点的单链表进行存储，每个结点有编号（数字）、数量和后继指针3个域。现在售出num台编号为x的计算机，试编写一个函数修改原单链表，且如若售完需删除该结点。 参照：typedef struct node linklist; deletex(linklist *head, int x) 一 选择题 1 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动 个数据元素。a 2.在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行b a.q next p s next p b.s next p q nex... 第1章。1.从逻辑上可以把数据结构分为。a 动态结构 静态结构 b 顺序结构 链式结构。c.线性结构 非线性结构 d 初等结构 构造型结构。2.关于算法的描述，不正确的是。a.算法最终必须由计算机程序实现。b 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。c.健壮的算法不会因非法的输人数... 一 选择题。1 广度优先遍历的含义是 从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问，直至图中所有已被访问的顶点的邻接点都被访问到是下图的广度优先遍历序列。a.1 ...数据结构练习
数据结构练习
数据结构练习