当前位置:首页 >> 其它课程 >>

算法与程序设计试卷


一、绪论 ? (一)数据结构的研究对象: ? 数据结构的研究对象包括: 数据的各种逻辑结构和存储结构以及对数据的各种操作。 ? (二)算法的五个特征: ? 有穷性、确定性、可行性、输入、输出。 ? (三)算法的时间复杂度: ? T(n) = O(f(n)) ? T(n)叫算法的渐进时间复杂度,简称时间复杂度, O 为数量级。 习题: ? 1、写出下列算法的时间复杂度。 ? (1)

for(i=0;i<n;i+ +) ? c[i]=i; O(n) ? (2)for(i=0;i<m;i+ +) ? for(j=0;j<n;j+ +) ? a[i][j]=i*j; O(mn) ? 2、数据结构的研究对象包括( 数据的逻辑结构,数据的物理存储结构以及对数 据的各种操作) 。 ? 3、从逻辑上可以把数据结构分为(线性 )和(非线性) 两种类型。 二、线性表 ? (一)顺序表:

顺序表的存储结构: ? #define Maxsize maxlen ? typedef int elemtype; ? typedef struct ? { ? elemtype v[Maxsize]; ? int len; ? }sqlist; 习题:给出顺序表的结构定义,在顺序表 List 中元素数组下标位置 i 插入一个元素 x。 ? #define MAXSIZE 100 ? struct list //顺序表结构 ? { ? int v[MAXSIZE]; //元素数组 ? int len; //顺序表当前包含的元素个数

? }; ? typedef struct list List; ? int insert(List *L , int i , int x) ? { ? //略 ? } ? (二)单链表 ? 每个结点包括两个域:数据域、指针域。 ? 单链表存储结构: ? typedef struct node ? { ? elemtype data; ? struct node *next; ? } Lnode ,*linklist; 习题:给出单链表的结构定义,编写函数实现链表的插入和删除操作。 ? struct linknode //单链表结点结构 ? { ? int data; //结点数据 ? struct linknode *next; //后继结点指针 ? }; ? typedef struct linknode Lnode; ? (1)在结点 p 之后插入值为 x 的新节点 s ? void insert(Lnode *p,int x;) ? { ? } ? (2)将结点 p 的后继结点删除,并释放结点空间 ? void delete(Lnode *p) ? { ? } ? (三)单循环链表: ? 使单链表的最后一个节点的指针域的值不为 NULL, 而是指向头结点。这样,整个 链表就形成了一个环,这种链表称为单循环链表。

? 习题: ? ? ? ? ? ? ? 1.线性表若采用链式存储结构时,要求内存中可用存储单元的地址( D ) 。 A)必须是连续的 B)部分地址必须是连续的 C)一定是不连续的 D)连续或不连续都可以 2.链表不具备的特点是(B ) 。 A) 插入和删除不需要移动元素 B)可随机访问任一节点 C) 不必预分配空间

D)所需空间与其长度成正比 3. 不带头结点的单链表 head 为空的判定条件是(A ) 。 A)head = = NULL B)head—>next = = NULL C)head—>next = = head D)head ! = NULL 4.带头结点的单链表 head 为空的判定条件是( B ) 。 A)head = = NULL B)head—>next = = NULL C)head—>next = = head D)head ! = NULL 5.带头结点的循环单链表 head 为空的判定条件是( C ) 。 A)head = = NULL B)head—>next = = NULL C)head—>next = = head D)head ! = NULL 6.在单链表中,指针 p 指向元素为 x 的结点,实现“删除 x 的后继”的语句是 ( B )。 ? A)p=p->next; B)p->next=p->next->next; ? C)p->next=p; D)p=p->next->next; ? 7.在长度为 n 的顺序表的第 i(1≤i≤n+1)个位置上插入一个元素,元素的移动次数 为___n-i+1_______ 。 三、栈和队列 ? (一)栈 ? 栈(Stack) 是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先出 的线性表,简称 LIFO 线性表 。 ? 顺序栈的顺序存储结构: ? #define maxsize 100//栈的最大容量 ? typedef struct ? { ? elemtp elem[maxsize]; ? int top; ? }sqstacktp; ? (二)队列 ? 队列(queue )是限定只能在表的一端进行插入,在表的另一端进行删除的线性表。 ? 队尾(rear)——允许插入的一端; ? 队头(front)——允许删除的一端。 ? 队列特点:先进先出(FIFO)或后进后出(LILO)。 ? 顺序队列的存储结构: ? #define maxsize 100 ? typedef struct ? { ? elemtp elem[maxsize]; ? int rear,front; ? }squeuetp; ? rear 指示队尾元素; ? front 指示队头元素前一位置。 ? 循环队列:把队列设想成环形。 ? 为了区分队空、队满状态,少用一个元素空间:front 所指单元不放元素。 ? 队空:sq.front==sq.rear

? ? ? ? ? ? ? ? ? ? ?

? 习题: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

队满:(sq.rear+1)%M==sq.front

1.栈是限定在( C )处进行插入或删除操作的线性表。 A)端点 B)栈底 C)栈顶 D)中间 2.栈的特点是( B ) 。 A)先进先出 B)后进先出 C)后进后出 D)不进不出 3.顺序栈存储空间的实现使用( B )存储栈元素。 A)链表 B)数组 C)循环链表 D)变量 4.顺序栈是空栈的条件是( A ) 。 A)top= =0 B)top= =1 C)top= =-1 D)top= =m 5.元素 A、B、C、D 依次进顺序栈后,栈底元素是( A ) 。 A)A B)B C)C D)D 6.队列是限定在( B )处进行删除操作的线性表。 A)端点 B)队头 C)队尾 D)中间 7.队列的特点是( A ) 。 A)先进先出 B)后进先出 C)先进后出 D)不进不出 8. 容量是 10 的循环队的头指针的位置 Sq->front 为 2, 则队头元素的位置是 (A ) 。 A)3 B)2 C)1 D)0 9.循环队列 Sq 是空队列的条件是( A ) 。 A)Sq-﹥rear= =Sq-﹥front B)(Sq-﹥rear+1)%maxsize= =Sq-﹥front C)Sq-﹥rear= =0 D)Sq-﹥front= =0 10.循环队列 Sq 是满队列的条件是( B ) 。 A)Sq-﹥rear= =Sq-﹥front B)(Sq-﹥rear+1)%maxsize= =Sq-﹥front C)Sq-﹥rear= =0 D)Sq-﹥front= =0 11.存放循环队列 Sq 元素的数组 data 有 10 个元素, Sq-﹥front 为 9,队头元素的位置在( A ) 。 A)10 B)9 C)1 D)0 12 用一维数组设计栈, 初态是栈空, top=0。 现有输入序列是 a、 c、 经过 push、 b、 d, push、pop、push、pop、push、pop、pop 操作后,输出序列是_b c d a_________。 ? 13 设将 a,b,c,d 依次入栈,则执行 push(a), pop(), push(b), push(c), pop(), pop(), push(d), pop(), 则出栈序列是__a c b d______ 。 五、树 ? (一)树的基本概念 ? 结点的度——结点拥有的子树数。 ? 叶子——度为 0 的结点,也叫终端结点。 ? 分支结点——度不为 0 的结点,也叫非终端结点。 ? 内部结点——除根结点之外,分支结点也称为内部结点。

树的度——一棵树中最大的结点度数。 孩子——结点子树的根称为该结点的孩子。 双亲——孩子结点的上层结点叫该结点的双亲。 兄弟——同一双亲的孩子之间互成为兄弟。 (二)二叉树的概念和性质 二叉树——二叉树是结点的有限集合,这个集合或者是空的,或者由一个根结点或 两棵互不相交的称为左子树的和右子树的二叉树组成。 ? 满二叉树——深度为 k 的满二叉树,是由2k -1个结点的深度为 K 的二叉树。2 k -1个结点是二叉树所具有的最大结点个数。 ? 完全二叉树——具有 n 个结点、深度为 K 的二叉树,当且仅当其所有结点对应于深 度为 k 的满二叉树中编号由 1 到 n 的那些结点时,该二叉树便是完全二叉树。 ? 二叉树的性质: ? 性质 1 在二叉树第 i 层上至多有2i - 1 个结点(i≥1) 。 ? 性质 2 深度为 k 的二叉树至多有2k-1 个结点(k≥1) 。 ? 性质 3 包含 n(n>0)个结点的二叉树的分支边数为 n-1。 ? 性质 4 对任何一颗二叉树 T,如果其终端结点(叶子结点)数为 n0 ,度为 2 的 结点数为 n2 , 则 n0 = n2+1。 (三)二叉树的链式存储结构
PARENT

? ? ? ? ? ?

LCHILD (a)

RCHILD

LCHILD DATA RCHILD (b) LCHILD DATA PARENT RCHILD (c)

二叉链表的类型定义: struct bnodept { datatype data; struct bnodept *lchild,*rchild }; typedef struct bnodept *bitreptr;

(四)二叉树的三种递归遍历算法 ? 遍历:是按一定的规则和次序走遍二叉树的所有结点,使每个结点都被访问一次, 而且只被访问一次。 ? 遍历二叉树的目的:得到二叉树中各结点的一种线性顺序,使非线性的二叉树线性 化。 ? 三种递归遍历算法: ? (1)先根序遍历 ? (2)中根序遍历 ? (3)后根序遍历 写出下图所示完全二叉树的先序、中序、后序序列:

习题: ? 二叉树的结构声明如下,写出实现二叉树的先序、中序、后序遍历算法。 ? 二叉树结点的结构: ? struct treenode ? { ? char data; ? struct treenode *lChild,*rChild; ? }; ? typedef struct treenode Tnode; ? (1)先序遍历递归算法 ? void preOrder( TNode *t ) ? { ? //略 ? } ? (2)中序遍历递归算法 ? void inOrder( TNode *t ) ? { ? //略 ? } ? (3)后序遍历递归算法 ? void postOrder( TNode *t ) ? { ? //略 ? } (五)线索二叉树 ? 线索:指向前驱或后继结点的指针称为线索。 ? 线索二叉树: 加上了线索的二叉链表称为线索链表, 相应的二叉树称为线索二叉树。 ? 对二叉树进行某种形式遍历使其变为线索二叉树的过程叫线索化,在遍历过程中, 用线索取代空指针即可。 ? 添加线索的方法:首先要确定是何种“序”的线索化(先序、中序还是后序) ,只有 空指针处才能加线索。结点无左孩子时,添加左线索,指向结点的前驱;结点无右 孩子时,添加右线索,指向结点的后继。 ? 习题:教材 P171 5.26 (六)哈夫曼树 ? 哈夫曼树:又称最优二叉树,是带权路径最短的树。 ? 树的带权路径长度:树中所有叶子结点的带权路径长度之和。

? 哈夫曼树的构造方法: ? (1)根据给定的 n 个权值{w1,w2,...,wn}构造 n 棵二叉树的集合 F={T1,T2,...,Tn} ; (2)在 F 中选取两棵根结点的权值为最小的树作为左、右子树以构造一棵新的二 叉树; (3)将新的二叉树加入到 F 中,删除原两棵根结点权值最小的树; (4)重复(2)和(3)直到 F 中只含一棵树为止,这棵树就是哈夫曼树。 习题:教材 P172 5.32 习题: ? 1.在一棵具有五层的满二叉树中,结点总数为( A ) 。 ? A)31 B)32 C)33 D)16 ? 2.在一棵二叉树中,第 5 层上的结点数最多为( C ) 。 ? A)8 B)15 C)16 D)32 ? 3.将一棵有 100 个结点的完全二叉树从上到下,从左到右依次对结点进行编号, 根结点的编号为 1,则编号为 49 的结点的左孩子编号为( B ) 。 ? A)99 B)98 C)50 D)48 ? 4.将含 100 个结点的完全二叉树从根这一层开始,按从上到下从左到右依次对结 点编号,根结点的编号为1。编号为 50 的结点 X 的双亲的编号为( A ) 。 ? A)25 B)48 C)100 D)无法确定 ? 5.已知一棵二叉树的先序遍历序列为 EFHIGJK,中序遍历序列为 HFIEJGK,则 该二叉树根的右子树的根是__G___________ 。 ? 6. 设先序遍历某二叉树的序列为 ABCD, 中序遍历该二叉树的序列为 BADC, 则后 序遍历该二叉树的序列为___BDCA__________。 ? 7. 二叉树使用二叉链表存储, p 指针指向二叉树的一个结点, p->lchild==NULL 若 当 时,则( A ) 。 ? A)p 结点左孩子为空 B)p 结点有右孩子 ? C)p 结点右孩子为空 D)p 结点有左孩子 ? 8.哈夫曼树是访问叶结点的带权路径长度( A )的二叉树。 ? A)最短 B)最长 C)可变 D)不定 ? 9.在完全二叉树中,如果一个结点是叶子结点,则它( C ) 。 ? A)一定没有左孩子结点,可能有右孩子结点 ? B)一定没有右孩子结点,可能有左孩子结点 ? C)一定没有左、右孩子结点 ? D)一定没有左、右孩子结点和兄弟结点 六、图 ? 1、图 ? 图是一种数据结构,其形式化定义可写为: G=(V,E) ? 其中,V 是顶点集合,E 是边或弧的集合。 ? 结论: ? 在具有 n 个顶点的有向图中,边的数目范围是 0~ n(n-1),拥有 n(n-1)条边的有向图 称为有向完全图。 ? 在具有 n 个顶点的无向图中,边的数目范围是 0~ n(n-1)/2,拥有 n(n-1)/2 条边的无 向图称为无向完全图。 ? 2、度、出度、入度 ? 无向图中,顶点的度为与每个顶点相连的边数。

? ? ? ? 习题: ? ? ? ? ? ? ? ? ? ? ? ? ?

有向图中,顶点的度分成入度与出度: 入度:以顶点 v 为头的弧的数目称为 v 的入度,记为 ID(v); 出度:以顶点 v 为尾的弧的数目称为 v 的出度,记为 OD(v); 顶点 v 的度为: TD(v)=ID(v)+OD(v) (1)在一个具有 n 个结点的无向图中,要连通全部结点至少需要( C ) 。 A)n 条边 B)n+1 条边 C)n-1 条边 D)n/2 条边 (2) 在一个有向图中, 所有顶点的入度之和等于所有顶点的出度之和的 ( B ) 。 A)1/2 倍 B)1 倍 C)2 倍 D)4 倍 (3)有 n 个结点的无向图的边数最多为( B ) 。 A)n-1 B)n(n-1)/2 C)n(n-1) D)2n(n-1) (4)有 n 个结点的有向图的边数最多为( C ) 。 A)n-1 B)n(n-1)/2 C)n(n-1) D)2n(n-1) (5)图的广度优先遍历类似于二叉树的( D ) ,深度优先遍历类似于二叉 树的( A ) 。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 (6)设某无向图中边数为 e,所有顶点的度数之和为 d,则 e=__d/2_____。 (7)设有向图用邻接矩阵 A[n][n]作为存储结构,则该邻接矩阵中第 i 列上所有元 素之和等于顶点 i 的___入度_____,第 i 行中所有非零元素个数之和等于顶点 i 的 ____出度____。 3、连通、连通图 连通:在无向图 G 中, 如果从顶点 v 到顶点 v'有路径,则称 v 和 v'是连通的。 连通图:如果对于图中任意两个顶点 vi,vj∈V,vi,vj 都是连通的,则称 G 是连 通图。 4、生成树、网、最小生成树 生成树:一个连通图的生成树是一个极小连通子图,它含有图的全部顶点,但只有 足以构成一棵树的 n-1 条边。 网:边带权的图称网。 最小生成树:最小生成树指的是( C ) 。 A)由连通图所得到的边数最少的生成树 B)由连通图所得到的顶点相对较少的生成树 C)连通图的所有生成树中边上的权值之和最小的生成树 D)连通图的极小连通子图 由无向连通图构造最小生成树的方法: (1)从图中任意顶点开始,将其包括在最小生成树中; (2)再选取权值最小的边,使其一个顶点已在生成树中,而另一个顶点尚不在生 成树中,将该顶点加入生成树。 (3)重复上步,直至所有顶点都包括在生成树中。这就是最小生成树。 Prim 算法的基本思想: 设 N=(V,E)是连通网,T=(V,E?)是正在构造中的生成树。 (1)初始状态时, 这棵生成树只有一个结点,没有边,即:U={u0},E?={ },u0 是任意选定的顶点; (2)在所有 u∈U,v∈V-U 的边(u,v)中找一条代价最小的边(u?,v?)并入集合 E?,

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

同时 v?并入集合 U; ? (3) 重复(2) 直到 V=U 为止。 , ? 此时,E?中必含有 n-1 条边,则 T=(V,E?)为 N 的最小生成树。 ? 习题:对 P216 图 6.38 所示的连通图,利用 Prim 算法构造其最小生成树。 ? Kruskal 算法的基本思想: ? 假设 N=(V, E)是连通网,将 N 中的边按权值从小到大的顺序排列: ? (1)令最小生成树的初始状态为只有 n 个顶点而无边的非连通图 T=(V,Φ ),图中 每一个顶点自成一个连通分量; ? (2)在 E 中选择权最小的边。若此边依附的顶点落在 T 中不同的连通分量上,则 将此边加入到 T 中,否则舍去此边而选择下一条代价最小的边。 ? (3)重复(2) ,直到 T 中所有的顶点都在同一连通分量为止。 习题:对下图所示的连通图,利用 Kruskal 算法构造其最小生成树。

七、查找 ? 1、静态查找表与动态查找表 ? 静态查找表与动态查找表二者的根本差别在于( D ) 。 ? A)它们的逻辑结构不一样 ? B)施加在其上的操作不同 ? C)所包含的数据元素的类型不一样 ? D)存储实现不一样 ? 静态查找表只能“查找”的操作,动态查找表还能进行插入、删除操作。 ? 有序表的的折半查找的时间效率为__O(log2n)________。 ? 2、二叉排序树 ? 二叉排序树或者是一棵空树;或者是具有下列性质的二叉树: ? ⑴ 若左子树不空,则左子树上所有结点的值均小于根结点的值; ? 若右子树不空,则右子树上所有结点的值均大于根结点的值。 ? ⑵ 左右子树也都是二叉排序树。 ? 对二叉排序树进行中序遍历,可得到一个按关键字有序的序列(从小到 大的序列) 。 ? 二叉排序树的生成: ? 二叉树的生成过程是逐个插入结点的过程。 ? 插入结点原则:若二叉排序树为空,则插入结点应为新的根结点;否则, 继续在其左、右子树上查找,直至某个结点的左子树或右子树为空为止,则插入结 点应为该叶子结点的左孩子或右孩子。 ? 二叉排序树生成:从空树出发,经过一系列的查找、插入操作之后,可

生成一棵二叉排序树。 ? 习题:给出关键字序列:63、90、70、55、67、42、98、83、10、45、 58,构造一颗二叉排序树。 ? 3、哈希表 ? 哈希表是一种特殊的“查找表”,在哈希表中,依据关键字能直接得到其 对应的数据元素位置,即在记录的关键字与记录的存储地址之间建立了一一对应关 系。这是由哈希函数来实现的。 ? 采用哈希表查找法需要解决的两个问题是:_哈希函数的建立____和__解 决冲突的方法__。 ? 例题:P242 7.12 习题: ? (1)设哈希表长 m=14,哈希函数 H(key)=key%11。表中已有 4 个结点: addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址为空,如用二次探测处 理冲突,关键字为 49 的结点的地址是___9____。 ? (2)若根据查找表建立长度为 m 的哈希表,采用线性探测法处理冲突, 假定对一个元素第一次计算的哈希地址为 d ,则下一次的哈希地址为 ( B ) 。 ? A) d B) (d+1)%m C) (d+1)/m D) d+1 八、排序 ? 1、稳定的排序方法: ? 直接插入排序、二路归并排序、冒泡排序; ? 不稳定的排序方法: ? 堆排序、快速排序、直接选择排序、希尔排序。 ? 2、在排序算法中,每次从未排序的记录中挑出最小(或最大)关键字 的记录,加入到已排序记录的末尾,该排序方法是( A ) 。 ? A. 选择排序 B. 冒泡排序 C. 插入排序 D. 堆排序 ? 3、冒泡排序的算法思想、冒泡排序的过程状态:P253-254 ? 习题:若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序,需进 行 ( C )次比较。 ? A)3 B)10 C)15 D)25 ? 4、快速排序的算法思想、快速排序的过程状态:P255-256


相关文章:
高二算法与程序设计考查试题及答案
高二算法与程序设计考查试题及答案_其它课程_高中教育_教育专区。2013 年高二信息技术(算法与程序设计)试题卷一、单项选择题(每小题 2.5 分共 50 分 将正确答案...
算法与程序设计期中试题_E卷
华东师范大学 2014 年~2015 第二学期 算法与程序设计基础 期中测验(E 卷)(本试卷答卷时间为 90 分钟)特别注意: 1.试卷提交前请不要关机或重启动,也不要将...
《算法与程序设计》试题带答案
算法与程序设计试题带答案_工学_高等教育_教育专区。《算法与程序设计试题带答案 高一第二学期《算法与程序设计》学分认定试题学校:___ 班级:___ 学号...
算法与程序设计历年会考题2014
算法与程序设计》选修模块历年会考试题 2013 年会考试题算 法与程序设计 》历年会 考试题 1 2012 年会考试题算 法与程序设计 》历年会 考试题 2 《...
算法与程序设计复习测试题
算法与程序设计复习测试题_其它课程_高中教育_教育专区。高中计算机《算法与程序设计》(选修)教材复习题 高二年级算法与程序设计复习检测一、 选择题:每题 2 分,...
《信息技术基础》与《算法与程序设计》试题
《信息技术基础》与《算法与程序设计试题 一、单选题(每题 2 分,共 30 分) 1、 小明想给远方的朋友传送一个 100M 大的文件, 那么他可以通过什么方式来...
高考算法与程序设计试题及答案
高考算法与程序设计试题及答案_其它课程_高中教育_教育专区。算法与程序设计高考题 编辑:桐乡第一中学 杜宗飞 A.算法与程序设计一、选择题(本大题共 17 小题,...
算法与程序设计练习卷
算法与程序设计练习卷(一) 班级 姓名 1、 下列是用计算机解决“猴子摘桃”问题的三个步骤: ① 编制计算机程序,用计算机进行处理 ② 分析问题,确定计算机解题任务...
算法与程序设计模拟试卷
算法与程序设计模拟试卷_其它课程_高中教育_教育专区。模拟试卷(一) A.算法与程序设计一、选择题:本大题 13 小题,每小题 2 分,共 26 分。在每小题给出的...
高二算法与程序设计试题及答案
高二信息技术(算法与程序设计)试题卷一、单项选择题(每小题 2.5 分共 50 分 将正确答案填到答题卷相应题号下) 1、一同学想通过程序设计解决“鸡兔同笼”的...
更多相关标签:
算法设计与分析 试卷 | 算法设计期末试卷 | 算法与程序设计 | 分形算法与程序设计 | 算法与程序设计ppt | 高中算法与程序设计 | 程序设计的典型算法有 | 算法与程序设计 教案 |