客观题
1单选(5分)
数据的_________可以表示数据元素之间的关系在计算机中的表示。
A.数据结构
B.数据之间的关系
C.数据的存储结构
D.数据的逻辑结构
正确答案：C
2单选(5分)
若一个算法中的语句频度之和T(n)=10n+59nlogn，则算法的时间复杂度为_________。
A.O(logn)
B.O(n+logn)
C.O(nlogn)
D.O(59logn)
正确答案：C
3单选(5分)
线性表采用顺序存储时，其地址 。
A.连续与否均可以
B.部分地址必须是连续的
C.一定是不连续的
D.一定是连续的
正确答案：D
4单选(5分)
二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则A的第8列和第5行共占 个字节。
A.114
B.54
C.150
D.108
正确答案：D
5单选(5分)
对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{9，15，7，8，20，-1，4}，则采用的排序方法是 。
A.希尔排序
B.选择排序
C.直接插入排序
D.堆排序
正确答案：C
6单选(5分)
设广义表L=（（a,b,c）），则L的长度和深度分别为_________。
A.
1和1
B.1和3
C.1和2
D.2和3
正确答案：C
7单选(5分)
在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是 。
A.快速排序
B.直接插入排序
C.冒泡排序
D.简单选择排序
正确答案：B
8单选(5分)
深度为K的二叉树中结点总数（ ）。
A.=2k-1
B.<2k-1
C.<=2k-1
D.2k
正确答案：C
9单选(5分)
冲突指的是（ ）。
A.两个元素的键值相同
B.两个元素具有相同序号
C.不同关键字记录对应相同的存储地址
D.两个元素的键值不同
正确答案：C
10单选(5分)
栈和队都是（ ）。
A.顺序存储的线性结构
B.链式存储的非线性结构
C.限制存取点的线性结构
D.限制存取点的非线性结构
正确答案：C
11判断(5分)
顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A.√
B.×
正确答案：B
12判断(5分)
已知带头结点的双向循环链表L，判断其为空表的条件是L->nextL && L->priorL。
A.√
B.×
正确答案：A
13判断(5分)
静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
A.√
B.×
正确答案：A
14判断(5分)
字符串常用的存储方式有：顺序串、堆串、块链串。
A.√
B.×
正确答案：A你选对了
15判断(5分)
一个稀疏矩阵Amn采用三元组顺序表形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Amn的转置运算。
A.×
B.√
正确答案：A
16判断(5分)
多维数组可以看作是一种特殊的线性表。
A.×
B.√
正确答案：B
17判断(5分)
求稀疏图的最小生成树，用克鲁斯卡尔算法来求解较好
A.√
B.×
正确答案：A
18判断(5分)
哈希查找是通过计算关键字的存储地址进行查找的一种方法。
A.×
B.√
正确答案：B
19判断(5分)
链式存储的优点是可以随机存储。
A.×
B.√
正确答案：A
20判断(5分)
串’student’和’Student’相等。
A.×
B.√
正确答案：A
主观题
1( 30分 )
1.假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。
typedef struct node{ ElemType data; struct node *next; }LNode, *LinkList;
回答：
void delete(Dlist *s){ LNode *p=s->next,*temp; while(p->next!=s){ temp=p; p=p->next; } temp->next=s; free(p); }
2( 40分 )
2. 编写算法，在以二叉链表存储的二叉树中，交换二叉树各结点的左右子树。
typedef struct node{ char data; struct node *Lchild，*Rchild; }BiTNode, *BiTree;
回答：
BiTNode* invertTree(BiTNode* root) { if (root == NULL) { return NULL; } BiTNode* left = invertTree(root->left); BiTNode* right = invertTree(root->right); root->left = right; root->right = left; return root; }
3( 30分 )
3. 请简单阐述图的存储结构有哪几种？图的遍历方式有哪几种？并结合实际谈谈图结构在实际生活中的应用。
回答： 图的存储结构有5种：邻接矩阵，邻接表，逆邻接表，十字链表，多重链表。 图的遍历有2种：深度优先遍历，广度优先遍历。 生活应用：生成最小树——城市交通问题最节省经费，拓扑排序——汽车装配工程，高校教学计划，关键路径——计算工程工期 和最短路径问题——城市交通中转最少路线。
最后也是及格了
