2017年浙江温州大学数据结构考研真题.doc-资料库

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

2017 年浙江温州大学数据结构考研真题）。）运算。）进行。 p＝HL; HL＝p; B. 错误的 B. 读表元 C. 查找 D. 定位 B. 14 C. 16 p->next＝HL; ）个不同的字符串？ B. p->next＝HL; D. p->next＝HL->next; HL->next＝p; 一、单项选择题（每小题 3 分，共 45 分） 1、线性表中的每一个元素都有一个前驱和后继元素。这个断言是（ A. 正确的 2、线性表的链接实现有利于（ A. 插入 3、在一个带有头结点的单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行（）。 A. HL＝p; C. p->next=Hl; 4、字符 A、B、C、D 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ A. 15 5、采用链结构存储线性表时，其结点地址（ A. 必须是连续的 C. 部分地址必须是连续的 6、队列的删除操作是在（ A. 队首 B. 队尾 7、当利用大小为 N 的数组顺序存储一个栈时，假定用 top=N 表示栈空，则退栈时，用（语句修改 top 指针。 A. top++; 8、二叉树的第 i 层上最多含有结点数为（ A. 2i 9、完全二叉树中，若一个结点没有左孩子，则它必是叶子。这个断言是（ A. 正确的 10、不使用递归也可实现二叉树的先序、中序和后序遍历。这个断言是（ A. 正确的 11、对于下图的 AOE 网中，计算顶点 4 所表示的事件最早发生时间 ve(4)是（ B. 连续不连续都可以 D. 必须是不连续的）。 C. 2i-1 C. top--; D. top=N; ）。）。 B. top=0; C. 队前 D. 对后 B. 2i-1-1 B. 错误的 B. 错误的 D. 21 ）。））。 D. 2i+1-1 B. 11 A. 6 12、采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。这个断言是（）。 A. 正确的 B. 错误的 C. 12 D. 13

B. 5 D. 7 ）。 B. 30, 150 C. 40, 130 D. 50, 130 C. 6 ）。说明：如果树只有一个结点，深度为 1。 13、已知数据序列为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ A. 4 14、有一棵平衡二叉树，它的广义表表示为 40(30, 130(60, 150))，在它中插入关键字 50 后，重新调整重新调整得到一棵新平衡二叉树，在新平衡二叉树中，关键字 60 所在结点的左、右子结点的关键字分别是（ A. 30, 130 15、对不稳定的排序算法，不论采用何种描述方式，总能举出一个说明它不稳定的实例来。这个断言是（ A. 正确的二、简答题（每个小问 5 分，共 35 分） 1、已知二叉树的后序遍历序列为 41253，中序遍历序列为 45213，则它的先序遍历序列？ 2、以｛3，7，8，2，6，10，14｝为，权值构造一棵 Huffman 树，这棵 Huffman 树的 WPL？ 3、对于下图，按照 Kruskal 算法构造它的一棵最小生成树，拭写出在最小生成树中依次得到的各条边。）。 B. 错误的 4、对一组关键字序列{20，66，34，98，15，53，21，58，2，10，44，30}，散列函数为 H(key) = key % 13，表长为 13。用线性探测法（F(i)=i）处理冲突，计算在等概率情况下查找成功的平均查找长度和查找不成功的平均查找长度。 5、给定关键字序列{72，87，61，23，94，16，5，58}，建小根堆。画出小根堆。 6、设一组初始记录关键字序列{5，2，6，3，8}，以第一个记录关键字 5 为基准进行一趟快速排序的结果？三、算法填空题（每空 2 分，共 30 分） 1、本题针对线性表的链式存储结构，完成相应的算法。 typedef int ElementType;

Node{ struct data; *next; /*使 p 指向单链表的第 1 个结点*/ typedef ElementType struct Node }Node, *LinkList; void outputList (LinkList L) /*输出带头结点的单链表*/ { Node *p; （1） ; while(p!=NULL){ printf(p->data); （2） ; } } void insertHead(LinkList L, ElementType x)/*L 指向头结点。在单链表中插入一个结点。头插法*/ { /*开辟空间*/ （3） s->data=x; /*p 后移*/ ; ; ; row, col; /*非零元素的值*/ /*非零元素的行下标和列下标*/ /*链接*/ （4）（5） } 2、下面是三元组表的存储结构及相应的算法，完成相应的算法。 typedef struct{ int ElementType value; }Triple; #define MAXSIZE 1000/*非零元素个数最多为 1000*/ typedef struct{/*非零元素的三元组表*/ Triple int }TSMatrix; /*采用"列序递增"法, 将矩阵 A 转置为矩阵 B*/ void transposeTSMatrix(TSMatrix *A, { int col, t, p; B->m = A->n; B->n = A->m; B->number = A->number; data[MAXSIZE+1]; /*data[0]不用*/ m, n, number; （6） /*矩阵的行数 m, 列数 n 和非零元素个数 number*/ ) if(A->number>0) {

（8）（7） p=0;/*记录下标*/ for(col=1; col<= /*从头至尾扫描三元组表 A，寻找列为 col 的三元组进行转置*/ for( if(A->data[t].col==col){ （10） B->data[p].row = A->data[t].col; B->data[p].col = A->data[t].row; B->data[p].value = A->data[t].value; （9） ; t<= ; ; col++){/*三元组表 A 的列值*/ ; t++){ } } } } struct *ALGraph; VertexType; /*顶点信息*/ ALGraphStruct ALGraphStruct; /*指向下一条边的指针*/ MAXVEX 100 /*最大顶点数*/ char } 3、下面是图的邻接表存储结构及相应的算法，完成相应的算法。 #define typedef struct typedef typedef struct EdgeNode{ /*该边所指的顶点的位置*/ int adjVertex; int weight; /*边的权*/ struct EdgeNode *nextEdge; }EdgeNode; typedef struct VNode{ VertexType data; EdgeNode *firstEdge; /*指向第一条依附该顶点的边的弧指针*/ }VNode; struct ALGraphStruct{ VNode vexs[MAXVEX]; int vertexNum,edgeNum; /*图的当前顶点数和弧数*/ }; /*在无向网中插入一条边。插入的边结点作为边链表的第 1 个结点。如果待插入的边已存在, 存储小权值。*/ void addEdge(ALGraph g, VertexType v1, VertexType v2, int w) { EdgeNode *s,*t; int i=locateVertex(g, v1); int j=locateVertex(g, v2); if(i==-1 || j==-1) （11） s=findEdge(g, i, j); if(s!=NULL){ /*找顶点 v1 的位置*/ /*找顶点 v1 的位置*/ ;

; t=findEdge(g, j, i); if(s->weight>w){ s->weight=w; （12） } return; } s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjVertex=j; s->weight=w; （13） g->vexs[i].firstEdge =s; t=(EdgeNode*)malloc(sizeof(EdgeNode)); t->adjVertex=i; t->weight=w; （14） g->vexs[j].firstEdge =t; ; ; ; （15） } 四、算法设计题（共 40 分） 1、按照给定的函数原型完成冒泡排序。（10 分） /*冒泡排序（升序）*/ void bubbleSort(int int n); r[], /*容量*/ 2、下面是顺序表的结构，设计一个高效算法，在顺序表中删除所有元素值为 x 的元素，要求空间复杂度为 O(1)。假设顺序表的数据元素类型为整型。（10 分） typedef int ElementType; typedef struct{ ElementType *array; /*存放元素的数组*/ int length; /*已经有多少元素*/ int capacity; }SeqList; 3、下面是哈夫曼树的存储结构，按照给定的函数原型完成求哈夫曼编码算法。（20 分） #define N 20 typedef int int int int }HTNode, HTree; /*从叶子结点到根, 逆向求每个叶子结点对应的哈夫曼编码*/ /*第 1 个参数存储哈夫曼树，第 2 个参数存储哈夫曼编码，第 3 个参数是叶子数*/ void createHuffmanCode(HTree ht[], char *hc[], int n); weight; parent; left; right; /*右孩子结点的下标*/ /*结点的权值*/ /*双亲的下标*/ /*左孩子结点的下标*/ /*叶子结点数*/ struct{

资料库

2017年浙江温州大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料