网站建设及,电子商务网站建设与管理课程的感想,湖南手机版建站系统信息,2024北京又开始核酸了吗今天这里写目录标题 选择题函数题6-1 求链式表的表长6-2 逆序数据建立链表6-3 删除单链表偶数节点6-4 求二叉树高度6-5 先序输出叶结点 选择题
2-1 下述程序段的时间复杂度为#xff08; #xff09;
for#xff08;i0; in-1; i#xff09;for#xff08;j0; jn-1-i… 这里写目录标题 选择题函数题6-1 求链式表的表长6-2 逆序数据建立链表6-3 删除单链表偶数节点6-4 求二叉树高度6-5 先序输出叶结点 选择题
2-1 下述程序段的时间复杂度为
fori0; in-1; iforj0; jn-1-i; jta[j], a[j]a[j1], a[j1]t;A.O(1) B.O(n) C.O(n2) D.O(n3 )、
答案C。 显然循环执行的次数是n-1) (n-2) ··· 1 O(n2)
2-2 下列对顺序存储的有序表长度为 n实现给定操作的算法中平均时间复杂度为 O(1) 的是 A.查找包含指定值元素的算法 B.插入包含指定值元素的算法 C.删除第 i1≤i≤n个元素的算法 D.获取第 i1≤i≤n个元素的算法
答案D **顺序表获可以通过访问下标取第 i个元素时间复杂度 O(1) **
2-3 将线性表La和Lb头尾连接要求时间复杂度为O(1)且占用辅助空间尽量小。应该使用哪种结构 A.单链表 B.单循环链表 C.带尾指针的单循环链表 D.带头结点的双循环链表 答案C 线性表La和Lb头尾连接要先找La的尾和Lb的头。对于带尾指针的单循环链表尾结点的next即为头结点而带头结点的双循环链表虽然也可以通过头结点的prev找到尾结点题目要求占用辅助空间尽量小选C
2-4 已知头指针 h 指向一个带头结点的非空单循环链表结点结构为 data | next其中 next 是指向直接后继结点的指针p 是尾指针q 是临时指针。现要删除该链表的第一个元素正确的语句序列是
A.h-nexth-next-next; qh-next; free(q); B.qh-next; h-nexth-next-next; free(q); C.qh-next; h-nextq-next; if (p!q) ph; free(q); D.qh-next; h-nextq-next; if (pq) ph; free(q);
答案D
2-5 假设有5个整数以1、2、3、4、5的顺序被压入堆栈且出栈顺序为3、5、4、2、1那么为了获得这样的输出堆栈大小至少为 A.2 B.3 C.4 D.5
答案C
2-6 有六个元素以6、5、4、3、2、1的顺序进栈问哪个不是合法的出栈序列 A.2 3 4 1 5 6 B.3 4 6 5 2 1 C.5 4 3 6 1 2 D.4 5 3 1 2 6
2-7 若栈采用顺序存储方式存储现两栈共享空间V[m]top[i]代表第ii1或2个栈的栈顶栈1的底在V[0]栈2的底在V[m-1]则栈满的条件是 A.|top[2]-top[1]|0 B.top[1]top[2]m
C.top[1] top[2] D.top[1]1top[2] 答案D 栈满的条件是两个栈的栈顶指针相遇。因为在顺序存储结构中当两个栈的栈顶指针相邻时表示两个栈的空间已经满
2-8 循环队列的队满条件为 ( ) A.(sq.rear1) % maxsize (sq.front1) % maxsize B.(sq.front1) % maxsize sq.rear C.(sq.rear1) % maxsize sq.front D.sq.rear sq.front
答案C
2-9 表达式a*(bc)-d的后缀表达式是 A.a b c * d - B. a b c d * - C.a b c * d - D.- * a b c d
答案A 根据选项的后缀表达式还原即可A是a(bc)-dB是a-(bcd)C是abc-dD纯扯淡一眼顶真是前缀*
2-10 数组A[1…5,1…6]每个元素占5个单元将其按行优先次序存储在起始地址为1000的连续的内存单元中则元素A[5,5]的地址为 A.1120 B.1125 C.1140 D.1145 答案C 如图自己算
2-11 二叉树中第5层根的层号为1上的结点个数最多为 A.8 B.15 C.16 D.32 答案C 二叉树中第n层结点数最多为2n-1
2-12 一棵二叉树中双分支结点数为15单分支结点数为30则叶子结点数为个。 A.15 B.16 C.17 D.47 答案B ** 对于n个结点的二叉树n n0n1n2; n0 n2 1带入求解即可**
2-13 以二叉链表作为二叉树的存储结构在具有 n 个结点的二叉链表中n0空链域的个数为 __ A.n1 B.n C.n−1 D.无法确定 答案A 有n个结点说明有2n个指针域又因为n个结点的二叉树有n-1条边那么空指针域就有2n-(n-1)n1
2-14 如果二叉树的后序遍历结果是FDEBGCA中序遍历结果是FDBEACG那么该二叉树的前序遍历结果是什么 A.ABCDEFG B.ABDFEGC C.ABDFECG D.ABDEFCG 答案C
2-15 设每个d叉树的结点有d个指针指向子树有n个结点的d叉树有多少空链域 A.nd B.n(d−1) C.n(d−1)1 D.以上都不是 答案C 跟2-13一模一样
2-16 已知一棵二叉树的树形如下图所示其后序序列为{ e, a, c, b, d, g, f }。树中与结点a同层的结点是
A.c B.d C.f D.g
答案B
2-17 下列线索二叉树中用虚线表示线索符合后序线索树定义的是
A.
B.
C.
D. 答案B 因为是后序线索树选项中树的后序遍历为dbca因此d的前驱为NULL排除CD后继为b排除A
2-18 具有65个结点的完全二叉树其深度为根的深度为1 A.8 B.7 C.6 D.5 答案B 具有n个结点的完全二叉树的深度 ⌊ log2n ⌋ 1
2-19 设一段文本中包含字符{a, b, c, d, e}其出现频率相应为{3, 2, 5, 1, 1}。则经过哈夫曼编码后文本所占字节数为 A.40 B.36 C.25 D.12 答案C
2-20 由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树该树的带权路径长度为 A.23 B.37 C.44 D.46 答案C 同上
函数题
6-1 求链式表的表长
本题要求实现一个函数求链式表的表长。
函数接口定义
cint Length( List L );
其中List结构定义如下
typedef struct LNode *PtrToLNode;
struct LNode {ElementType Data;PtrToLNode Next;
};
typedef PtrToLNode List;L是给定单链表函数Length要返回链式表的长度。
裁判测试程序样例
#include stdio.h
#include stdlib.htypedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {ElementType Data;PtrToLNode Next;
};
typedef PtrToLNode List;List Read(); /* 细节在此不表 */int Length( List L );int main()
{List L Read();printf(%d\n, Length(L));return 0;
}/* 你的代码将被嵌在这里 */输入样例 1 3 4 5 2 -1 输出样例 5
解
int Length( List L )
{int ret 0;while(L){ret;L L-Next;}return ret;
}6-2 逆序数据建立链表
本题要求实现一个函数按输入数据的逆序建立一个链表。
函数接口定义
cstruct ListNode *createlist();
函数createlist利用scanf从输入中获取一系列正整数当读到−1时表示输入结束。按输入数据的逆序建立一个链表并返回链表头指针。链表节点结构定义如下
struct ListNode {int data;struct ListNode *next;
};裁判测试程序样例
#include stdio.h
#include stdlib.hstruct ListNode {int data;struct ListNode *next;
};struct ListNode *createlist();int main()
{struct ListNode *p, *head NULL;head createlist();for ( p head; p ! NULL; p p-next )printf(%d , p-data);printf(\n);return 0;
}/* 你的代码将被嵌在这里 */输入样例 1 2 3 4 5 6 7 -1 输出样例 7 6 5 4 3 2 1 解
struct ListNode* createlist()
{struct ListNode* head (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur head;cur-next NULL;int tmp 0;scanf(%d,tmp);while(tmp ! -1){cur-data tmp;scanf(%d,tmp);struct ListNode* tmp (struct ListNode*)malloc(sizeof(struct ListNode));tmp-next cur;cur tmp;}return cur-next;}6-3 删除单链表偶数节点
本题要求实现两个函数分别将读入的数据存储为单链表、将链表中偶数值的结点删除。链表结点定义如下
struct ListNode {int data;struct ListNode *next;
};函数接口定义
struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );函数createlist从标准输入读入一系列正整数按照读入顺序建立单链表。当读到−1时表示输入结束函数应返回指向单链表头结点的指针。
函数deleteeven将单链表head中偶数值的结点删除返回结果链表的头指针。
裁判测试程序样例
#include stdio.h
#include stdlib.hstruct ListNode {int data;struct ListNode *next;
};struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );
void printlist( struct ListNode *head )
{struct ListNode *p head;while (p) {printf(%d , p-data);p p-next;}printf(\n);
}int main()
{struct ListNode *head;head createlist();head deleteeven(head);printlist(head);return 0;
}/* 你的代码将被嵌在这里 */输入样例 1 2 2 3 4 5 6 7 -1 输出样例 1 3 5 7 解
struct ListNode *createlist()
{struct ListNode* head (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur head;cur-data -1;cur-next NULL;int tmp 0;while ( tmp ! -1){scanf(%d, tmp);if(tmp ! -1){struct ListNode* ts (struct ListNode*)malloc(sizeof(struct ListNode));cur-next ts;ts-data tmp;ts-next NULL;cur ts;}}return head-next;
}struct ListNode *deleteeven( struct ListNode *head )
{if(head-next NULL){if(head-data%2 0)return NULL;elsereturn head;}struct ListNode *ret head;while(ret-data%2 0){struct ListNode* del ret;ret ret-next;free(del);if(ret-next NULL){if(ret-data%2 0)return NULL;elsereturn ret;}}struct ListNode * cur ret;while(cur-next){if(cur-next-data%2 0){struct ListNode* del cur-next;cur-next cur-next-next;free(del);}elsecur cur-next;}return ret;
}6-4 求二叉树高度
本题要求给定二叉树的高度。
函数接口定义
int GetHeight( BinTree BT );其中BinTree结构定义如下
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};要求函数返回给定二叉树BT的高度值。
裁判测试程序样例
#include stdio.h
#include stdlib.htypedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
int GetHeight( BinTree BT );int main()
{BinTree BT CreatBinTree();printf(%d\n, GetHeight(BT));return 0;
}
/* 你的代码将被嵌在这里 */输出样例对于图中给出的树 4 解
int max(int a,int b)
{return ab?a:b;
}
int GetHeight( BinTree BT )
{if(BT NULL)return 0;return max(GetHeight(BT-Left),GetHeight(BT-Right))1;
}6-5 先序输出叶结点
本题要求按照先序遍历的顺序输出给定二叉树的叶结点。
函数接口定义
void PreorderPrintLeaves( BinTree BT );其中BinTree结构定义如下
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点格式为一个空格跟着一个字符。
裁判测试程序样例
#include stdio.h
#include stdlib.htypedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
void PreorderPrintLeaves( BinTree BT );int main()
{BinTree BT CreatBinTree();printf(Leaf nodes are:);PreorderPrintLeaves(BT);printf(\n);return 0;
}
/* 你的代码将被嵌在这里 */输出样例对于图中给出的树 Leaf nodes are: D E H I 解
void PreorderPrintLeaves( BinTree BT )
{if(BT NULL)return;if(BT-Left NULL BT-Right NULL){printf( %c,BT-Data);return;}PreorderPrintLeaves(BT-Left);PreorderPrintLeaves(BT-Right);
}
