《数据结构A卷.doc》由会员分享，可在线阅读，更多相关《数据结构A卷.doc（12页珍藏版）》请在三一文库上搜索。
1、For personal use only in study and research; not for commercial use羁试卷 A莆膄一、单项选择题袂 1. 算法的时间复杂度取决于（ C ）螈 A问题的规模B.待处理数据的初态C. A和 BD.以上都不是虿 2一个算法应该是（B）。薃A程序B问题求解步骤的描述C要满足五个基本特性D A 和 C.薂 3从逻辑上可以把数据结构分为（C）两大类。螀 A动态结构、静态结构B顺序结构、链式结构螇 C 线性结构、非线性结构D初等结构、构造型结构芇 4设无向图的顶点个数为 n，则该图最多有（ B ）条边。莃 A n-1B n(n-1)/2C n
2、(n+1)/2D 0袁 5程序段 FOR i:=n-1 DOWNTO 1 DO袅FOR j:=1 TO i DO蚆IF Aj>Aj+1肃THEN Aj与 Aj+1对换；蚈其中 n 为正整数，则最后一行的语句频度在最坏情况下是（D）A. nB. nlognC. n32芈D. n膆 6线性表是具有n 个（ C）的有限序列（ n>0）。袄 A表元素B字符C数据元素D 数据项蚀 7.静态链表中指针表示的是（C） .莆 A 内存地址B数组下标C下一元素地址D左、右孩子地址薅 8.对于栈操作数据的原则是（B）。薄 A. 先进先出B.后进先出C.后进后出D.不分顺序螁 9.图中有关路径的定义是（
3、A）。蝿 A 由顶点和相邻顶点序偶构成的边所形成的序列B由不同顶点所形成的序列羄 C由不同边所形成的序列D上述定义都不是芄 10对于前序遍历与中序遍历结果相同的二叉树为（B） ;薈 A一般二叉树B所有结点只有右子树的二叉树C 根结点无左孩子的二叉树袇 D根结点无右孩子的二叉树蒄螁薀羅二、判断题袃薁 1. 数据元素是数据的 最小 ( 基本 ) 单位。 ( )蚁 2.数据的逻辑结构是指数据的各数据项之间的逻辑关系； ()莈 3算法可以用不同的语言描述， 如果用 C 语言或 PASCAL语言等高级语言来描述， 则算法实际上就是程序了。 ( )薆 4.数据结构的抽象操作的定义与具体实现有关。()芁 5
4、.链表中的头结点仅起到标识的作用。( )葿 6.顺序存储结构的主要缺点是不利于插入或删除操作。( Y )蒆 7.栈与队列是一种特殊操作的线性表。（ Y）羆 8. 二叉树是度为 2 的有序树。 ( )肂 9.完全二叉树一定存在度为1 的结点。 ( )薀 10在 n 个结点的无向图中，若边数大于n-1, 则该图必是连通图。 （）袈莅三、填空题螂 1.对于给定的n 个元素 , 可以构造出的逻辑结构有集合，线性结构，树形结构， _图状结构或网状结构_四种。集合线性结构树形结构图状结构或网状结构。薁 2栈是 _的线性表，其运算遵循_的原则。操作受限后进先出羇 3二叉树由 _根结点 _ ， _左子树_，_
5、右子树_三个基本单元组成。根结点左子树右子树袅 4.循环队列的引入，目的是为了克服_。假溢出时大量移动数据元素蒃荿 四、算法设计题（可以用 C语言和任何算法描述语言答题，所有算法设计题都已经假设按默认初始化）荿 1. 有如下定义：芄 #define MAXLEN 100/*顺序表存储空间的总分配量*/芃 #define OK 1蒀 #define ERROR 0蒈 #define OVER -1蚃 typedef int ElemType;/*定义 ElemType 为 int类型 */羃 typedef struct蒂薆 ElemTypedataMAXLEN;/*存放线性表的数组*/莇 in
6、t Length;/*Lengthgth是顺序表的长度*/螄 SeqList;艿给出顺序表的插入算法。羈螆 /*插入函数 */蒄 int InsElem(SeqList *L, int i, ElemType x)莀 肇 int j;芅 if (L->Length>=MAXLEN)羀 莂 printf ("表已满！ ");葿 return OVER;/*表满，不能插入*/蚅蚁 if (i<1 | i>L->Length+1)/*检查给定的插入位置的正确性*/腿薇 printf(" 插入位置出错！ ");肄 return ER
7、ROR;蒁芀 if (i = L->Length+1)蚆 蒄 L->datai-1=x;膂 L->Length+;莂 return OK;/*插入的位置为表尾，则不需移动直接插入即可*/肈羃 for (j=L->Length-1; j>=i-1; j-) /*结点移动 */羂 L->dataj+1=L->dataj;腿 L->datai-1=x;/*新元素插入 */膇 L->Length+;/*表长度增1 */蚆 return OK;/*插入成功，返回*/蚂 膁蕿肆 2 有如下定义：蒃 typedef charElemType;/*定义 E
8、lemType 为 char 类型 */羈 typedef struct node/*链栈存储类型 */蚇 蒅ElemTypedata;/*定义结点的数据域 */膃struct node*next;/*定义结点的指针域 */聿 LinkStack;螆给出取栈顶元素算法。袄袃 int EmptyStack(LinkStack *S)肁 膈 if(S=NULL)/*栈为空 */莄return 1;蚄 else袈return 0;芆 螃 int GetTop(LinkStack *S,ElemType *x)莄 罿 if(EmptyStack(S)/*调用判空函数EmptyStack(S) ，判断栈
9、是否为空*/蕿 蒇printf("栈空 !");袀return 0;羁 螇 else/*栈不为空 */袆 薁*x=S->data;/*栈顶元素赋给变量x*/螈return 1;袆 芅 莁衿膈 3. 有如下定义：螅 typedef char ElemType;/*定义 ElemType 为 char 类型 */肂 #define MAXSIZE 100/*顺序队列存储空间的总分配量*/羁 typedef struct /*顺序队列存储类型*/莆 ElemTypedataMAXSIZE;/*存放顺序队列的数组*/膄 int front;/*记录队头元素位置的变量*/袂 i
10、nt rear;/*记录队尾元素位置的变量*/螈 SeqQueue;虿给出入队算法。薃薂 int EnQueue(SeqQueue *Q,ElemType x)螀 螇 if(Q->rear+1)%MAXSIZE=Q->front)/*队列为满 */芇 莃printf("队满 !");袁return 0;/*队满不能入队*/袅 蚆 else/*队不为满 */肃 蚈Q->rear=(Q->rear+1)%MAXSIZE;/*队尾指针增1*/芈Q->dataQ->rear=x;膆return 1;袄 蚀 莆薅 4. 有如下定义：薄 #defin
11、e NULL 0/*螁 #define MaxSize 100/*蝿 typedef char ElemType;/*羄 typedef struct tnode芄 ElemType data;/*薈 struct tnode *lchild,*rchild; /*袇 BTNode;蒄 给出前 ( 根) 序遍历二叉树的递归算法。螁薀 void PreOrder(BTNode *bt)/*羅 if(bt=NULL) return;/*袃else薁 printf("%c",bt->data);/*蚁PreOrder(bt->lchild);/*莈PreOrder(b
12、t->rchild);/*薆 芁 葿蒆羆 5. 有如下定义：定义空指针为0*/树的最大元素个数为100*/定义 char 为 ElemType 类型 */数据域 */左、右孩子指针*/前序遍历二叉树BT*/递归调用的结束条件*/输出结点的数据域*/前序递归遍历左子树*/前序递归遍历右子树*/肂 #define MaxSize1000/*顺序表的表长*/薀 typedef int KeyType;袈 typedef int ElemType;莅 typedef struct螂 薁KeyType key;/*存放关键字，KeyType 为关键字类型*/羇ElemType data;/*其他数
13、据,ElemType为其他数据的类型*/袅 LineList;蒃给出顺序查找和有监视哨的顺序查找算法。荿荿 /* 顺序查找函数 */芄 int SeqSearch(LineList r,int n,KeyType k)芃 蒀int i=1;/*与改进算法相匹配，查找表范围从下标1.n*/蒈 while (i<=n &&ri.key!=k) i+;蚃 if(i>n)羃 return(-1);蒂 else薆 return(i);莇 螄艿 /* 改进顺序查找 */羈 int SeqSearch1(LineList r,int n,KeyType k)螆 蒄 int i=n
14、;莀 r0.key=k;肇 while (ri.key!=k)芅i-;羀return(i);莂 葿蚅6. 有如下定义：蚁 #define MaxSize 100/*线性表中最多元素个数*/腿 typedef int KeyType;/*关键字类型 */薇 typedef char ElemType; /*其他类型数据项类型*/肄 typedef struct蒁 芀 KeyType Key;/*关键字域 */蚆 ElemType data;/*其他数据项 */蒄 LineList;膂给出冒泡排序算法。莂肈 /*冒泡排序 */羃 void BubbleSort1(LineList r, int n
15、)羂 int i,j;腿 LineList temp;膇 for (i=n-1;i>0;i-)蚆 蚂 for (j=0;j<=i-1;j+)膁 if(rj.Key>rj+1.Key)蕿肆temp=rj;rj=rj+1;rj+1=temp;蒃羈 蚇 蒅以下无正文仅供个人用于学习、研究；不得用于商业用途。 , .For personal use only in study and research; not for commercial use.Nur f ü r den pers?nlichen fü r Studien, Forschung, zu kommerziellen Zwecken verwendet werden.Pour l 'é tude et la recherche uniquementà des fins personnelles; pasà des fins commerciales.