201203学期《算法与数据结构》复习纲要a
一、单选题。
1. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（ ）
a. 单链表b. 静态链表。
c. 线性链表d. 顺序存储结构。
2. 用单链表表示的链队的对头在链表的（ ）位置。
a. 链头b. 链尾
c. 链中 d. 任意。
3. （是c语言中的“abcd321abcd”的子串（ ）
a. abcdb. 321ab
c. “abcabcd. “21ab”
4. 一个n*n的对称矩阵，如果以行或者列为主序放入内存，则容量为（ ）
a. n*n b. n*n/2
c. n*(n+1)/2 d. (n+1)2/2
5. 递归函数f(n)=f(n-1)+n (n>1)递归出口是（ ）
a. f(1)=0b. f(1)=1
c. f(0)=1d. f(n)=n
6. 有如下递归过程：
void reverse （int m）
printf （“d”，n%10）；
if （n/10!=0）
reverse (n/10);
调用语句reverse（582）的结果是（ ）
a. 582b. 852
c. 258d. 285
7. 树最适合用来表示（ ）
a. 有序数据元素 b. 无序数据元素
c. 元素之间具有分支层次关系的数据 d. 元素之间无联系的数据。
8. 顺序查找法适合于存储结构为（ ）的线性表。
a. 散列存储b. 顺序存储或链式存储。
c. 压缩存储d. 索引存储。
二、多选题。
1. 数据是信息的载体，它有（ ）几种形式。
a. 整数和实型数 b. 字符串。
c. 图像和声音 d. 信息。
e. 磁盘文件。
2. 在算法分析与数据结构中，算法描述方法有（ ）
a. 自然语言 b. 框图。
c. 类计算机语言 d. 数据结构。
3. 常用的线性表存贮结构有（ ）
a. 顺序存贮结构 b. 链表存贮结构。
c. 队列存贮结构 d. 堆栈存贮结构。
e. 顺序存贮与链表存贮混合结构。
4. 一维数组元素的类型可以是（ ）
a. 简单变量，如整数、浮点数b. 复合变量，如结构体、数组。
c. 只有简单变量d. 指针变量。
e. 字符串。
5. 假设以链表的方式实现堆栈，top为栈顶指针，指向类型为linkstack类型，下述程序。
实现将堆栈初始化为空栈的操作。程序（ ）是正确的。
a. void initstack( linkstack *top )
top = null;};
b. void initstack(linkstack * top )
top = 1;};
c. void initstack(linkstack * top )
top = 0;};
d. void initstack(linkstack * top )
top =空；};
6. 下列排序算法中哪些是不稳定的？（
a. 冒泡排序 b. 选择排序。
c. 快速排序 d. 堆排序。
三、填空题。
1. 数据结构针对数据对象，要研究其逻辑结构及其操作。
2. 算法设计要求达到以下目标可读性、健壮性、高效率与低存储要求。
3. 栈的特点是因此栈又称为表。
4. 队列的特点是因此队列又称为表。
5. 假定二叉树的数据域为data, 左右子树的指针域分别是lchild和rchild，指向根结点。
的指针为t, 完善以下二叉树前序遍历的算法。
preorder(t)
if (t==null)
return;
printf(t->data);
6. 冒泡排序算法在最好情况下，比较次数是。
7. 针对插入与删除操作，顺序文件效率不高。如果需要在顺序文件上实现插入与删除操作，解决问题的基本方法是。
8. 下面的算法是从数组a中删除第i个元素起的k个元素。试补充完整程序。
* arraysize 指数据的尺寸，last是数据中已有的元素个数。*/
algorithm delk(int a[arraysize], int i, int k, int last)
if (!k >=0) &1 <=i +k &&i +k <=last )&0 <=last &&last <=arrary))
/*判断参数合法性 */
printf(“error !”
else for (count = 1; count <=k; count++)
/*删除一个元素 */
for(j = last; j>= i +1; j--)
last = last – 1;
四、判断题。
1. 线性表中的元素只能是简单类型。（
2. 线性表是数组。（
3. 如果入队与出队的操作顺序不同，其输出元素的顺序可以与输入元素的顺序不同。（
4. 栈满是数据对象栈的固有操作。（
5. 二叉树只有前序、中序和后序三种遍历运算。（
6. 数据结构中只研究了二叉树，对一般树没有给出解决问题的算法。（
7. 在单向链表中，在x指向的结点后插入结点，对应的方法与x是否是头指针无关。（
8. 分块查找时引入了静态查找就是顺序查找、折半查找和分块查找。（
9. 在求最短路径的dijkstra算法和floyd算法中，dijkstra算法只能求从一点到其他各。
点的最短路径，而floyd算法可以求图中两点之间的最短路径。（
10. 树是一种特殊的图。（
五、简答题。
1. 对链表设置头结点的作用是什么？（至少说出两条好处）
2. 在hq的链队中，设计一个算法求该连队中结点的个数。
3. 假设有如下的结构定义：
struct node
char data;
struct node * link;
p, *pre;
而且pre指向链表中非空元素，写一段程序生成构造p结点，并将其链入到pre之后。
4. 求1到n的平方和（利用递归函数调用）
5. 为什么要采用循环队列？
201203学期《算法与数据结构》复习纲要a答案
一、单项选择题。
二、多项选择题。
三、填空题。
1）物理结构 （2）正确性 （3）先进后出，先进后出 （4）先进先出，先进先出。
5）preorder(t->lchild);
preorder(t->rchild);
6） n-17）批处理8）a[j-1] =a[j]
四、判断题。
五、简答题。
1 答：其好处有：
1）对带头结点的链表，在表的任何接点之前插入结点或删除表中的任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结点（若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除结点时操作复杂些）。
2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
2 答：求该链队中结点个数实际上是计算以hq->front为头指针的单链表中的结点个数。算法如下：
int qucount (lqueue *hq)
return (n);
3 ch=getchar取一个数据元素//
p=(struct node *)malloc(sizeof(struct node));
申请一个新结点//
p->data=ch;
p->link = pre->link;
pre->link = p;
4 答：int sum2（int n）
if （n==0）return 0；
return sum2（n-1）+n*n;
5答：以连续空间实现队列时，有可能造成大量的数据移动或队列假满的现象，采用循环队列可以避免队列假满或大量移动数据的问题。
数据结构与算法复习
第二部分模拟试卷。模拟试卷一。单选题 每题 2 分，共20分 以下数据结构中哪一个是线性结构？a.有向图 b.队列 c.线索二叉树 d.b树。在一个单链表hl中，第二部分模拟试卷。模拟试卷一。一 单选题 每题 2 分，共20分 1.以下数据结构中哪一个是线性结构？a.有向图 b.队列 c.线索二叉树...
数据结构与算法复习
数据结构与算法课程考试复习资料。一 填空题。a卷 arraylist类在。net框架的 命名空间中。a b卷 c 语言中，数组的基类是 array a b卷 c 语言中提供了两种类分别用来表示栈和队列，它们是。stack类和 queue类。a卷 查找指定字符的方法是 substring a卷 c 中...
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...