数据结构(本科)期末综合练习(算法设计题).DOC.doc
《数据结构(本科)期末综合练习(算法设计题).DOC.doc》由会员分享,可在线阅读,更多相关《数据结构(本科)期末综合练习(算法设计题).DOC.doc(15页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构(本科)期末综合练习(算法设计题).DOC数据结构(本科)期末综合练习(算法设计题)1. 设有一个线性表 (e0, e1, , en2, en1) 存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个元素内容置换为 (en1, en2, , e1, e0)。函数的原型为:templateclass Type void inverse ( Type A , int n );2。 试编写一个函数,在一个顺序表A中找出具有最大值和最小值的整数.函数的原型如下所示,原型的参数表中给出顺序表对象为A,通过算法执行,从参数表中的引用参数
2、Max中得到表中的最大整数,Min中得到表中的最小整数.注意,函数中可使用顺序表的两个公有函数:Length( ) 求表的长度;getData(int k) 提取第k个元素的值.include “SeqList.h” template class T void FindMaxMin ( SeqListint A, int Max, int Min );3。 设有两个整数类型的顺序表A(有 m个元素)和B(有n个元素),其元素均以升序排列。试编写一个函数,将这两个顺序表合并成一个顺序表C,要求C的元素也以升序排列(表中允许元素重复)。 函数的原型如下所示。原型中的参数表给出参加运算的三个顺序表A
3、、B与C.从C中得到执行结果。函数中用到顺序表的4个公有函数: Length( ) 求表的当前长度; maxLength( ) 求表的最大允许长度; getData(int k) 提取第k个元素的值; setData(int k, int val) 修改第k个元素的值为val. templateclass T void merge(SeqListint& A, SeqList& C);4。 编写一个函数frequency,统计在一个输入字符串中各个不同字符出现的频度。函数返回两个数组:A 记录字符串中有多少种不同的字符,C 记录每一种字符的出现次数。此外,还要通过整数k返回不同字符数。 函数的
4、原型如下所示: #include iostream.h #include data; p1 = p1-link; while ( p2 != NULL ) /继续处理p2链表中剩余的结点.p=p-link = new ListNode; p-data = p2data; p2 = p2link; plink = NULL; return firstlink;6. 假定在一个带表头结点的单链表L中所有结点的值按递增顺序排列,试补充下面函数,功能是删除表L中所有其值大于等于min,同时小于等于max的结点.void rangeDelete ( ListNode L, ElemType min, E
5、lemType max ) ListNode *q = L, p = L-link; 7。 已知一个带表头附加结点的单链表LA中包含有三类字符:数字字符;字母字符;其他字符。试编写一个while循环补充下面Separate函数,其功能是构造三个新的单链表,使LA,LB,LC单链表各自指向同一类字符.要求使用原表的结点空间.Separate函数将调用如下两个函数: bool isdigit(char ch); /判断字符是否为数字,若是则返回“真”,否则返回“假 bool isalpha(char ch); /判断字符是否为字母,若是则返回“真”,否则返回“假 void Separate ( L
6、istNode & LA, ListNode * LB, ListNode & LC ) /原来的单链表是LA, 新的三个单链表是LA,LB,LC,它们均需要带表头附加结点 ListNode *pa=LA; ListNode *pb=new ListNode, *pc=new ListNode; LB=pb; LC=pc; ListNode p=LA-link; /p指向待处理的结点 /添加的while循环位置 pa-link = NULL; pblink = NULL; pclink = NULL; /请把while循环内容写在此行下面8。 已知first为单链表的表头指针, 结点结构为(d
7、ata,link),试根据下列每个函数声明和算法功能写出递归算法。 int Max(LinkNode *f); /递归算法: 求链表中的最大值,若链表为空则返回0 int Num(LinkNode *f); /递归算法: 求链表中结点个数9。 请分别写出在循环队列上进行插入和删除操作的算法. 循环队列定义如下: struct CyclicQueue ElemType elemM; /M为已定义过的整型常量,表示队列长度 int rear,front ; / rear指向队尾元素后一个位置,front 指向队头元素 int tag ; / 当 front=rear且tag=0时,队列空,当fro
8、nt=rear且tag=1时,队列满 ; bool EnCQueue( CyclicQueue Q, ElemType x ) / Q 是一个循环队列,最多可存储M个元素,若队列不满, /将x插入至队尾并返回 true;否则返回 false。 bool DelCQueue( CyclicQueue& Q, ElemType& x ) / Q 是一个循环队列,若队列不空,则删除队头元素并由 x 带回, /且返回 true,否则返回 false 10. Q 是一个由其尾指针和队列长度标识的循环队列,请写出插入和删除一个元素的算法。 struct CyclicQueue / 循环队列定义 ElemT
9、ype elemM; /M为已定义过的整型常量 int rear; / rear指向队尾元素的后一个位置 int length; / length 指示队列中元素个数 ; bool EnCQueue( CyclicQueue Q, ElemType x ) /Q是一个循环队列,若队列不满,则将x插入并返回true;否则返回false bool DelCQueue( CyclicQueue Q, ElemType& x ) /Q 是一个循环队列,若队列不空,则删除队头元素并由x带回, /且返回true;否则返回false 11. 计算多项式 Pn (x) = a0 xn + a1 xn1 + a
10、2 xn2 + + an-1 x + an 通常使用的方法是一种递推的方法.它可以描述为如下的递推形式: pn (x) = x * pn-1 (x) + an (n0)此处 Pn1 (x) = a0 xn-1 + a1 xn2 + + an-2 x + an-1 P0=an这也是问题的递归形式.多项式的递归求解形式为:poly(x, 0) = A0poly(x, n) = x * poly(x, n-1) + An, n 0试编写一个递归函数,计算这样的多项式的值。float poly ( float x, float A, int n ) 12。 从n个自然数1, 2, 3, , n中任取k
11、个数的所有组合数用C(n, k) 表示。求C(n, k)的递归公式为 0 (n0, k=0或k=n) n (n0, k=1) C(n-1, k) + C(n1, k-1) (n1, 0kn)试写出计算C(n, k)的递归函数:int combine ( int n, int k) 13. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data;BinTreeNode *left, right;其中data为结点值域,left和right分别为指向左、右子女结点的指针域。根据下面函数声明编写出求一棵二叉树高度的算法,该高度由函数返回。假定树
12、根的层次为0,参数BT初始指向这棵二叉树的根结点。 int BTreeHeight(BinTreeNode* BT); 14。 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data;BinTreeNode *left, right;其中data为结点值域,left和right分别为指向左、右子女结点的指针域,根据下面函数声明编写出求一棵二叉树中结点总数的算法,该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。 int BTreeCount(BinTreeNode BT); 15. 已知二叉树中的结点类型BinTreeNode定
13、义为: struct BinTreeNode char data;BinTreeNode left, *right;其中data为结点值域,left和right分别为指向左、右子女结点的指针域,根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法,该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。 int BTreeLeafCount(BinTreeNode BT); 16. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data;BinTreeNode left, *right;;其中data为结点值域,left和right
14、分别为指向左、右子女结点的指针域,根据下面函数声明编写出删除一棵二叉树中所有结点的算法,并使树根指针为空。假定引用参数BT初始指向这棵二叉树的根结点. void ClearBTree(BinTreeNode* BT); 17. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data;BinTreeNode *left, right;;其中data为结点值域,left和right分别为指向左、右子女结点的指针域,根据下面函数声明编写出判断两棵二叉树是否相等的算法,若相等则返回1否则返回0.算法中参数T1和T2为分别指向这两棵二叉树根结点的指
15、针.当两棵树的结构完全相同并且对应结点的值也相同时才被认为相等。int BTreeEqual(BinTreeNode* T1,BinTreeNode T2); 18。 已知二叉树中的结点类型用BinTreeNode表示,被定义为: struct BinTreeNode char data;BinTreeNode *left, *right;其中data为结点值域,left和right分别为指向左、右子女结点的指针域,根据下面函数声明编写出交换一棵二叉树中所有结点的左、右指针域值的算法,算法中参数BT初始指向这棵二叉树的根结点。void BTreeSwop(BinTreeNode* BT) 19
16、。 已知二叉树中的结点类型用BinTreeNode表示,被定义为: struct BinTreeNode char data;BinTreeNode left, right;; 其中data为结点值域,left和right分别为指向左、右子女结点的指针域,根据下面函数声明编写出复制一棵二叉树的算法,并返回复制得到的二叉树的根结点指针。算法中参数BT初始指向待复制二叉树的根结点。 BinTreeNode* BTreeCopy(BinTreeNode BT); 20。 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data;BinTreeNo
17、de *left, *right;;其中data为结点值域,left和right分别为指向左、右子女结点的指针域,根据下面函数声明编写出从一棵二叉树中求出结点值大于X的结点个数的算法,并返回所求结果。算法中参数BT初始指向一棵二叉树的根结点。 int BTreeCount(BinTreeNode* BT, ElemType x); 21. 假定元素类型为ElemType的一维数组Rn中保存着按关键码升序排列的n个记录,记录的关键码域key的类型为KeyType,试按照下面的函数声明编写一个非递归算法,从一维数组Rn中折半搜索出关键码等于K的记录,若搜索成功则返回记录位置(即元素下标),否则返回
18、-1。 int BinSearch(ElemType R, int n, KeyType K); 22. 已知二叉搜索树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data;BinTreeNode *left, *right;;其中data为结点值域,left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树的根结点.试根据下面的函数声明编写一个非递归算法,从BST树中搜索出具有item参数值的结点,若搜索成功则返回该结点的地址,否则返回NULL。 BinTreeNode* Find(BinTreeNode BST
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 本科 期末 综合 练习 算法 设计 DOC
限制150内